SubsetsSubsets

01Why it exists

Reach for it when you see:All combinations, choose any number of them, each item wanted or not, the power set, every state of a set of switches, n small (≤ 20) and you need the whole list.

02The core idea

Subsets are the first lesson in backtracking because their decision tree is as simple as it gets: element i has exactly two options, take it or skip it. Start at nums[0], decide one element per level going down, and by level n every element has been decided — the path at that moment is one subset. With n elements and two choices each there are 2ⁿ leaves, and each subset corresponds to exactly one leaf, so nothing is repeated and nothing is missed.

The backtracking skeleton is three steps: make a choice (push nums[i] onto path), recurse (handle i+1), and undo the choice (pop nums[i] off path). The undo is the crucial part, because path is one single array shared by every recursive call. When control returns to the level above, path has to look exactly as it did before, or the next branch will build on the wrong state. When you collect an answer, copy it with path[:] — otherwise later pops will reach back in and mangle the subsets you already stored.

The complexity comes from two factors: there are 2ⁿ leaves and copying each subset costs O(n), giving O(2ⁿ·n). That cannot be improved, because each element appears in half the subsets, so just writing the answer out means printing n·2ⁿ⁻¹ numbers. The space is only the recursion depth plus path, O(n), not counting the output. This is also why backtracking only suits small n: n = 20 is about a million subsets, and n = 40 is over a trillion.

The other common shape decides "who goes next" at each level, using start to pick only to the right, so every node in the tree is a subset, not just the leaves. It looks the same as the combinations problem, and it handles duplicate elements more easily: sort first, then within a level skip any j where j > start and nums[j] == nums[j-1], because the branch that puts this value in this position has already been explored. The j > start part cannot be dropped: without it even [2, 2] disappears, since placing the same value again one level down would be skipped too.

03The algorithm

1. 1Set up ans (the answers) and path (the current path), and write dfs(i) to mean "deciding element i right now".
2. 2Base case: when i == len(nums) every element has been decided, so append a copy of path to ans.
3. 3Make a choice: path.append(nums[i]), then recurse with dfs(i + 1).
4. 4Undo the choice: path.pop(), restoring path to how it looked on entry to this level.
5. 5Take the other branch: skip nums[i] and call dfs(i + 1) directly. With both branches done, this level is finished and control returns to the level above.

04Interactive demo

The decision tree for [1, 2, 3]. Each node shows the path so far, the left branch takes the element and the right branch skips it. Notice how every undo rewinds the path to what it was on entering that level, and how the 8 leaves are exactly the 8 subsets.

05Code

Three versions: the standard take-or-skip shape, the start-index shape where every node is a subset, and the version that handles duplicate elements.

# Subsets (LeetCode 78): every element is either taken or skipped
def subsets(nums):
    ans = []
    path = []

    def dfs(i):
        if i == len(nums):            # every element has been decided
            ans.append(path[:])       # copy it: path keeps changing afterwards
            return
        path.append(nums[i])          # make a choice: take nums[i]
        dfs(i + 1)
        path.pop()                    # undo the choice
        dfs(i + 1)                    # the other branch: skip nums[i]

    dfs(0)
    return ans


# Another shape: each level decides who goes next, so every node is a subset
# start only lets you pick to the right, so [1, 2] and [2, 1] never both appear
def subsets_start(nums):
    ans = []
    path = []

    def dfs(start):
        ans.append(path[:])           # collect as soon as you enter a node
        for j in range(start, len(nums)):
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)
    return ans


# Subsets with duplicates (LeetCode 90): sort first, then skip repeated values within a level
def subsets_with_dup(nums):
    nums = sorted(nums)               # sorted() returns a new list, leaving the caller's input alone
    ans = []
    path = []

    def dfs(start):
        ans.append(path[:])
        for j in range(start, len(nums)):
            if j > start and nums[j] == nums[j - 1]:   # this value was already tried at this level
                continue
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)
    return ans


if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
    print(subsets_start([1, 2, 3]))
    # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    print(subsets_with_dup([1, 2, 2]))
    # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

06Practice

• LeetCode 78SubsetsMedium
• LeetCode 90Subsets II (sort, then skip duplicates within a level)Medium
• LeetCode 784Letter Case Permutation (each letter is upper or lower case)Medium
• LeetCode 1863Sum of All Subset XOR TotalsEasy
• LeetCode 2044Count Number of Maximum Bitwise-OR SubsetsMedium
• LeetCode 698Partition to K Equal Sum Subsets (each number picks a subset to join, with pruning)Medium