DSAMotivator

Subsets

Medium·🧭 Backtracking·Open on LeetCode ↗

Given distinct numbers, produce every possible selection of them — from taking none at all to taking all of them.

nums = [4, 7, 9]step 1/38
{ }

Every subset of {4,7,9} is one sequence of take/skip answers. Walk them as a tree.

1def subsets(nums):
2    res, path = [], []
3 
4    def dfs(i):
5        if i == len(nums):
6            res.append(path[:])
7            return
8        path.append(nums[i])
9        dfs(i + 1)
10        path.pop()
11        dfs(i + 1)
12 
13    dfs(0)
14    return res
Read the 38 steps as text
  1. 1Every subset of {4,7,9} is one sequence of take/skip answers. Walk them as a tree.
  2. 2At { } — the question is whether to take 4.
  3. 3Take 4. Everything below here contains it.
  4. 4At {4} — the question is whether to take 7.
  5. 5Take 7. Everything below here contains it.
  6. 6At {4,7} — the question is whether to take 9.
  7. 7Take 9. Everything below here contains it.
  8. 8No decisions left. Record {4,7,9}.
  9. 9Undo that — put 9 back. Now explore the subsets without it.
  10. 10No decisions left. Record {4,7}.
  11. 11Both branches under {4,7} are finished.
  12. 12Undo that — put 7 back. Now explore the subsets without it.
  13. 13At {4} — the question is whether to take 9.
  14. 14Take 9. Everything below here contains it.
  15. 15No decisions left. Record {4,9}.
  16. 16Undo that — put 9 back. Now explore the subsets without it.
  17. 17No decisions left. Record {4}.
  18. 18Both branches under {4} are finished.
  19. 19Both branches under {4} are finished.
  20. 20Undo that — put 4 back. Now explore the subsets without it.
  21. 21At { } — the question is whether to take 7.
  22. 22Take 7. Everything below here contains it.
  23. 23At {7} — the question is whether to take 9.
  24. 24Take 9. Everything below here contains it.
  25. 25No decisions left. Record {7,9}.
  26. 26Undo that — put 9 back. Now explore the subsets without it.
  27. 27No decisions left. Record {7}.
  28. 28Both branches under {7} are finished.
  29. 29Undo that — put 7 back. Now explore the subsets without it.
  30. 30At { } — the question is whether to take 9.
  31. 31Take 9. Everything below here contains it.
  32. 32No decisions left. Record {9}.
  33. 33Undo that — put 9 back. Now explore the subsets without it.
  34. 34No decisions left. Record { }.
  35. 35Both branches under { } are finished.
  36. 36Both branches under { } are finished.
  37. 37Both branches under { } are finished.
  38. 38All 8 subsets found — 2^3, one per root-to-leaf path.

Start with the obvious solution

Count from 0 to 2^n − 1, treat each number's bits as an include/exclude mask, and read off the subset each mask selects.

O(n · 2^n) time, O(n) extra space

Why that isn't enough: Nothing — it is genuinely optimal here, and worth saying out loud. The catch is that it is a trick, not a technique: the moment the problem adds duplicates or a pruning rule, the bitmask has nowhere to put them. The recursive form is the one that survives Subsets II and Combination Sum.

The idea

There are 2^n subsets, and the exponent is the hint: each element faces one independent yes/no question. Take it, or don't. Answer that question n times and you've named exactly one subset — so the subsets and the answer-sequences are the same thing counted twice.

That turns generating subsets into walking a binary tree. Level i asks about nums[i], the two branches are take and skip, and every root-to-leaf path spells out one subset. Nothing is ever ruled out, which is what makes this the gentlest possible backtracking problem: the shape of the search is visible without any pruning logic on top of it.

The word 'backtracking' describes one line — the pop. After exploring everything that follows from taking an element, you undo that choice so the same list can be reused for the branch that skips it. One list, mutated and restored, instead of a fresh copy at every node.

The approach

  1. 1Keep one running list `path` and a results list `res`.
  2. 2At index i, if i has run past the end, the decisions are all made — record a *copy* of path and return.
  3. 3Otherwise append nums[i] and recurse on i + 1. That explores every subset that contains nums[i].
  4. 4Pop it back off, and recurse on i + 1 again. That explores every subset that doesn't.
  5. 5Start at index 0 with an empty path.

Complexity

Time
O(n · 2^n)
Space
O(n)

There are 2^n subsets and copying each into the results costs up to O(n). The extra space is just the recursion depth and the single path list — the output itself is not counted.

Code

def subsets(nums):
    res, path = [], []

    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i])
        dfs(i + 1)
        path.pop()
        dfs(i + 1)

    dfs(0)
    return res

What goes wrong

  • •Appending `path` instead of a copy of it. Every entry in the results then aliases the same list, which you keep mutating, so you finish with 2^n references to one empty list. `path[:]` in Python, `new ArrayList<>(path)` in Java.
  • •Forgetting the pop. Without it the path only ever grows, and the 'skip' branch explores a state that the algorithm never actually chose.
  • •Assuming this needs a `visited` set or a duplicate check. It doesn't — distinct inputs plus a fixed left-to-right index order means no subset can be generated twice. Subsets II is the version where that stops being true.
  • •Reaching for a loop-based powerset with bitmasks and then being unable to adapt it. The bitmask trick is elegant and genuinely O(n · 2^n) too, but it doesn't generalise to the pruning problems this pattern exists to teach.