Subsets (LeetCode 78)

The problem

You get a list of distinct integers. Return every possible subset of it (the power set), including the empty subset and the full list. The order of the subsets doesn’t matter, but no subset may appear twice.

Input:  nums = [1, 2, 3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Three elements, each either in or out, gives 2³ = 8 subsets.

How to think about it

Start with brute force. Each element is either in a subset or not, so there are 2ⁿ subsets. You can’t beat that: the output itself has 2ⁿ entries. So the question isn’t “how do I go faster than exponential”, it’s “how do I generate each subset exactly once without a mess of duplicate checks”.

The naive trap. If at every step you’re allowed to pick any unused element, you’ll build [1,2] and also [2,1]. Those are the same subset. Removing duplicates afterwards with a set of tuples works, but it wastes time and looks sloppy in an interview.

The key insight: only pick elements to the right of the last one you picked. Pass a start index into the recursion. From a node, you may only add nums[start], nums[start+1], and so on. That forces every subset to be built in increasing index order, so [2,1] can never be built, and each subset has exactly one path in the tree.

Every node is an answer. Unlike permutations, you don’t wait until the path is “full”. The empty path at the root is a subset, [1] is a subset, [1,2] is a subset. So you record the path on entry to every call.

Which pattern is this? Backtracking: choose, recurse, undo. The tell is “return all subsets / all combinations”, where the answer is a list of every valid selection.

Approach

1. Keep a shared path list and a result list res.
2. bt(start, path) first appends a copy of path to res.
3. Then, for each index i from start to the end: append nums[i], recurse with bt(i + 1, path), then pop it off (undo).
4. Call bt(0, []) and return res.

Solution

def subsets(nums):
    res = []
    def bt(start, path):
        res.append(path[:])                  # every node is a subset: record a copy
        for i in range(start, len(nums)):
            path.append(nums[i]); bt(i + 1, path); path.pop()   # choose, recurse, undo
    bt(0, []); return res
# subsets([1,2,3]) -> 8 subsets ([], [1], [1,2], [1,2,3], [1,3], [2], ...)

Dry run

On nums = [1, 2, 3], in the order the calls happen:

Eight calls, eight subsets, no duplicates.

Complexity

• Time: O(n·2ⁿ). There are 2ⁿ nodes in the tree, one per subset, and copying each path costs up to O(n).
• Space: O(n) extra. The recursion depth and the path are at most n long. The output itself takes O(n·2ⁿ), which is not usually counted as extra space.

Edge cases and pitfalls

• Empty input returns [[]]: one subset, the empty one. Not [].
• Appending path instead of path[:]. Every entry in res would point to the same list, and you’d end with a list of empty lists after all the pops.
• Recursing with start + 1 instead of i + 1. That reuses elements and produces wrong subsets. The next start is always one past the element you just chose.
• Duplicates in the input break this version (you’d get [1,2] twice for [1,2,2]). That is Subsets II, which sorts and skips.

Related problems

• Subsets II (LeetCode 90): the same tree, with a skip rule for duplicate values.
• Subsets (bitmask enumeration) (LeetCode 78): the same problem solved by counting from 0 to 2ⁿ − 1.
• Combinations (LeetCode 77): the same start index, but only record paths of length k.