Backtracking

Backtracking searches a tree of decisions. At each step you choose, recurse, then undo so the next choice starts from a clean state. It is depth-first search on decisions you are generating, rather than on a graph you were handed.

Subsets are the smallest useful version. For each number, it is either in the subset or it is not, so you walk both branches. The copy of the current path matters. If you save the same array you are still mutating, later undos empty the subsets you thought you had kept. The undo is the pop. Forget it and every later subset inherits the previous choice.

This explodes. n distinct numbers have 2ⁿ subsets, and you list all of them. Backtracking is the right tool when the search space is modest, or when you can prune, for example stopping once a partial sum already exceeds the target. It is the wrong tool when a shorter dynamic-programming table would count the answers without listing them.