Notice Period
visualization

Backtracking: Subsets

Choose, explore, un-choose — the undo is what makes it work.

nums = [1, 2, 3] · enumerate all 2³ = 8 subsetsstep 1/23
{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}
current path = [] · recorded subsets
{}

Enter the root with an empty path — record {} first; the empty set is a subset too.

pseudocode
def backtrack(start, path):
    record(path[:])             # every node is a subset
    for i in range(start, len(nums)):
        path.append(nums[i])    # CHOOSE
        backtrack(i + 1, path)  # EXPLORE
        path.pop()              # UN-CHOOSE
# 2^3 = 8 subsets recorded