Why it works
- Every call stands for one subset, the path that led to it, so saving at the start of each call saves every subset; the tree has exactly 2ⁿ calls.
- A call adds only numbers after the last one taken (start = i + 1). Each subset is then built in one order only, smallest index first, so none is saved twice.
- Removing the number after the call comes back leaves the path as it was before it, so the next number of the loop starts from the same subset.
Complexity
Time O(n × 2ⁿ): 2ⁿ calls, and each copies a path of up to n numbers. Memory O(n) besides the answer: the path and the call stack are at most n deep.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗