1Understand
The idea
Each element gives you a choice: take it or skip it. Explore the choices recursively, adding the current partial result to the answer, and undo the last choice before trying the next one. Starting the next choice after the current index prevents the same combination in a different order.
Intuition
Each element gives a choice: take it or skip it. Explore recursively, record the current partial result when appropriate, and undo the last choice before trying the next branch.
Starting the next choice at i+1 (not 0) prevents the same combination in a different order. That is the difference between subsets/combinations and permutations.
The call tree has 2ⁿ leaves for subsets; pruning and early returns matter when constraints appear.
What you will be able to do
- Copy the path when recording
- Use a start index to avoid reordering
When to use it
- All subsets / combinations
- Combination sum
- Every way to choose k items
2See it
Walkthrough
Subsets of [1, 2]
Choose or skip each index; record path at every node.
1 / 4
Start with path []. Always record a copy of the current path (the empty subset too).
Live template
Line 1 active
Complexity: time O(2^n · n), space O(n)
Time O(n · 2ⁿ) to output all subsets. Space O(n) for the recursion path (plus O(n · 2ⁿ) for the answer). Iterative bit masks also work; recursion matches interview explanation better.
Read the walkthrough as text
All subsets of `[1,2,3]`.
- Start with path
[], index0. Record[]. - Choose
1: path[1]; from index 1 choose2→[1,2]then3→[1,2,3]; backtrack. - After exploring branches that include
1, try branches that start by skipping to2, then3. - Collected:
[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3].
In code:
def dfs(start, path):ans.append(path[:])for i in range(start, n):path.append(nums[i])dfs(i + 1, path)path.pop()
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
All subsets
Example. Return every subset of distinct integers.
How. At each index, branch include or skip; or for-loop with start index and push/pop path.
Subsets with duplicates
Example. Subsets when nums may repeat.
How. Sort; at each depth, skip duplicate values at the same start position.
Combinations of size k
Example. All k-combinations of 1..n.
How. Only extend from i+1 so order is increasing; stop when len(path) == k.
Combination sum (reuse allowed)
Example. All combos that sum to target, same candidate reusable.
How. Recurse from same index i after choosing candidates[i] (unbounded knapsack style).
Combination sum without reuse
Example. Each candidate used at most once.
How. After picking i, next call starts at i+1 so values are not reused.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Path not copied
Why it happens. Appending the live path list means every result points at the same mutable object.
How it fails. out.append(path); path.pop() at end, all entries look like [] in the output.
Fix. Record `out.append(path[:])` (or list(path)) at each leaf.
Duplicate combinations
Why it happens. Equal values at the same depth generate the same combination twice.
How it fails. nums = [1,2,2]: combos (1,2) from both 2s appear twice.
Fix. Sort; at depth, skip i > start when nums[i] == nums[i−1].
Wrong start index
Why it happens. Restart from 0 for combinations, or wrong index when reuse is allowed.
How it fails. Combination sum with reuse: recurse from i+1 only, can’t build [2,2,3] for target 7 with candidates [2,3].
Fix. No reuse: next start is i+1. Reuse allowed: next call still starts at i. Subsets: always i+1 for distinct picks.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.