Build every subset by making one decision per item: take it or leave it out. Each decision splits the search in two, so n items give a decision tree with 2ⁿ leaves, one per subset. The code chooses (push), explores, then un-chooses (pop) before trying the other branch, so a single list, cur, serves the whole search. Taking is always tried first, so the full set is recorded first and the empty set last.
- Average time
- O(n·2ⁿ)
- Space
- O(n)