Subsets

The Idea

A subset is one yes-or-no answer per item, so the decision tree is binary: skip nums[i], or take it and move on.

The index only ever moves forward, which is what stops {1, 2} and {2, 1} both appearing. Every leaf is a complete set of decisions, so there are exactly two to the power n of them — and the pop after the take branch is again what keeps the shared path honest.

Real-World Example

Choosing which optional modules to switch on for a build. Each flag is independent, and the release team wants every combination tested — eight builds for three flags, sixteen for four.

The Code

def subsets(nums, i, path, out):
    if i == len(nums):               # every item has been decided
        out.append(path[:])
        return
    subsets(nums, i + 1, path, out)  # branch 1: leave nums[i] out
    path.append(nums[i])             # branch 2: take it
    subsets(nums, i + 1, path, out)
    path.pop()                       # un-choose before returning

out = []
subsets([1, 2, 3], 0, [], out)
print(len(out))
print(out[:4])

out = []
subsets([1, 2, 3], 0, [], out)
print(len(out))