Subsets

Subsets is the "hello world" of backtracking. The answer is the whole search space, so there is nothing to prune — which makes it the cleanest place to see the choose–explore–undo shape on its own.

It is also the base for a family of harder questions: combinations of size k, subsets that hit a sum, subsets of a list with repeats. Get this one right in two different ways and the rest are small changes.

The problem

You are given a list of distinct integers. Return every subset of it — every way to pick some of the numbers, including picking none and picking all. The order of the subsets, and the order inside each subset, do not matter.

• [1, 2, 3] → [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. Three items give 2³ = 8 subsets.
• [7] → [[], [7]]. One item: take it or not.

Constraints: 1 ≤ n ≤ 10, values between −10 and 10, all distinct.

Clarifying questions

• Can the input contain repeats? Assume no here. The second half of this lesson handles repeats.
• Is the empty subset included? Yes — it is a valid subset, and forgetting it is a classic off-by-one.
• Does output order matter? No. Any order of subsets is accepted.
• Return values or indices? Values.

Approach 1: the simple way — count in binary

Each subset is a yes/no decision per element. Three elements, three decisions, so each subset matches a 3-bit number. 101 means "take element 0 and element 2" → [1, 3]. Count from 0 to 2ⁿ − 1 and read off the bits.

1def subsets_bits(nums: list[int]) -> list[list[int]]:2    """Every subset by reading the bits of 0 .. 2**n - 1."""3    n = len(nums)4    return [[nums[i] for i in range(n) if mask & (1 << i)]5            for mask in range(1 << n)]

Complexity: O(n × 2ⁿ) time — 2ⁿ masks, n bit checks each. O(n × 2ⁿ) for the output.

Here the honest answer is that this is not too slow. The output itself has n × 2ⁿ numbers in it, so nothing can beat O(n × 2ⁿ). For n = 10 that is about ten thousand steps. The weakness is different: a bit mask cannot stop early. The moment the problem adds a rule — "no repeated subsets", "only subsets that sum to 12" — the bit loop still builds every mask and filters afterwards. It cannot skip a doomed branch, because it has no branches. Backtracking does, and that is why interviewers want to see it here.

The key insight

A subset is built by walking the list once and making one decision per element: take it, or leave it. That is a binary tree of depth n with 2ⁿ leaves, one per subset. The diagram above shows the top of it for [1, 2].

There is a second way to draw the same space. Instead of "take or leave element i", ask "which element do I add next?", and allow only elements to the right of the last one added. Now each node is a different subset, and the tree has exactly 2ⁿ nodes, not 2ⁿ leaves. Both trees are correct. The second is the one that extends to combinations and to duplicates, so it is the one to know best.

Approach 2: take or leave

1def subsets_include_exclude(nums: list[int]) -> list[list[int]]:2    """Every subset: at each index, take nums[i] or leave it."""3    result: list[list[int]] = []4    path: list[int] = []56    def decide(i: int) -> None:7        if i == len(nums):              # every element has been decided8            result.append(path[:])      # record a copy9            return10        path.append(nums[i])            # take nums[i]11        decide(i + 1)12        path.pop()                      # undo13        decide(i + 1)                   # leave nums[i]1415    decide(0)16    return result

Each call decides one index. The first recursive call explores every subset that contains nums[i]; after the pop() the second explores every subset that does not. Answers are recorded only at the leaves, when all n decisions are made. On [1, 2, 3] it returns [1, 2, 3] first and [] last, because "take" is tried before "leave".

Approach 3: the start-index loop

1def subsets(nums: list[int]) -> list[list[int]]:2    """Every subset of distinct nums, built with a start index."""3    result: list[list[int]] = []4    path: list[int] = []56    def backtrack(start: int) -> None:7        result.append(path[:])              # every node is a subset8        for i in range(start, len(nums)):   # only elements after the last one taken9            path.append(nums[i])            # choose10            backtrack(i + 1)                # explore; never reuse index i11            path.pop()                      # undo1213    backtrack(0)14    return result

Three things to notice. The result is recorded at the top of every call, with no return, because every node is an answer. The loop starts at start, so the path is always in increasing index order and each set appears in exactly one order. And the call passes i + 1, so the same index is never taken twice.

Dry run on [1, 2, 3]:

Eight calls, eight subsets — exactly [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]], the order the code really returns.

Complexity: 2ⁿ calls, each doing an O(n) copy, so O(n × 2ⁿ) time. Working space is O(n): the path and a recursion stack at most n deep. The output is O(n × 2ⁿ) on top.

When the input has repeats (Subsets II)

Now allow repeated values: [1, 2, 2]. The plain template gives 8 subsets, but only 6 are different. [2] appears twice — once from the first 2, once from the second — and [1, 2] appears twice for the same reason.

The fix, derived. Sort first, so equal values sit next to each other. Now look at one loop. Taking the first 2 and then exploring already covers every subset that contains a single 2, and the subset [2, 2] too. Taking the second 2 in the same loop can only rebuild subsets the first 2 already produced. So: within one loop, skip a value equal to the one just tried.

But only within one loop. When the parent took the first 2, the child loop starts at the second 2 with i == start. Skipping it there would lose [2, 2], a real subset. The two 2s are at different depths, not rivals in the same loop. That gives the exact rule:

1def subsets_with_dup(nums: list[int]) -> list[list[int]]:2    """Every distinct subset when nums may contain repeats."""3    nums = sorted(nums)                      # equal values become neighbours4    result: list[list[int]] = []5    path: list[int] = []67    def backtrack(start: int) -> None:8        result.append(path[:])9        for i in range(start, len(nums)):10            if i > start and nums[i] == nums[i - 1]:11                continue                     # same value, same loop: already tried12            path.append(nums[i])13            backtrack(i + 1)14            path.pop()1516    backtrack(0)17    return result

On [1, 2, 2] it returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]] — six subsets, none repeated. In the root loop, i = 2 is skipped because nums[2] == nums[1] and 2 > 0. Inside the branch that took the first 2, i = 2 equals start, so it is allowed and [2, 2] appears.

The brute-force alternative is to build all 2ⁿ subsets and throw the repeats into a set of sorted tuples. It gives the same answer but always builds all 2ⁿ, even when the input is [4, 4, 4, 4, 4] and only 6 subsets are different. The skip rule builds exactly the 6.

Edge cases

• One element — [7] gives [[], [7]]. The root records [], one branch records [7].
• The empty subset — recorded by the very first call. Code that records only inside the loop misses it.
• All values equal — [4, 4, 4] must give 4 subsets: [], [4], [4, 4], [4, 4, 4]. Only the skip rule with i > start gets this right.
• Negative numbers — no effect; nothing compares values except the duplicate check.

Follow-ups

• Only subsets of size k (Combinations) — record only when len(path) == k, and stop the loop early when too few elements remain to reach k.
• Subsets that sum to a target — sort, keep a running total, and break the loop once adding nums[i] would pass the target.
• No recursion allowed — start with [[]], and for each number append it to a copy of every existing subset. Same O(n × 2ⁿ) cost.