Subsets (include / exclude)

53 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

List every possible team you can pick from three friends, 1, 2 and 3, including the empty team and the full team. By hand you might write: nobody, 1, 2, 3, 12, 13, 23, 123. Eight teams. You probably got there by some mix of memory and checking you had not missed one, and with four friends you would start to lose track. With twenty friends there are over a million teams, and "did I miss one?" is hopeless.

There is a cleaner way to count first. For each friend you make one decision, in or out, and the decisions are independent:

2 × 2 × 2 = 2³ = 8 teams, and 2ⁿ in general

The pattern turns that counting argument into a procedure that writes each team exactly once.

Build the structure, one piece at a time

Piece one: an index i that walks through the friends in order, 0, 1, 2. At each index you make the one decision for that friend.

Piece two: a path, which is the team built so far. It behaves like a stack: deciding "in" pushes the friend, and undoing that decision pops them.

Piece three: the rule, as a function solve(i): if i is past the last friend, record a copy of the path; otherwise push friend i, call solve(i + 1), pop friend i, and call solve(i + 1) again. "Take, recurse, untake, recurse."

The order the teams come out is a depth-first walk of a decision tree with 2 branches at every level and 2ⁿ leaves.

Why it is correct

The invariant: when solve(i) is called, the path holds exactly the friends among 0 .. i − 1 who were decided "in". It is true at the start (empty path, i = 0) and each call keeps it: pushing friend i then calling solve(i + 1) hands over a path that is correct for the "in" choice; popping restores the previous path before the "out" choice. Each sequence of decisions is tried exactly once, so each team is recorded exactly once, and every team corresponds to some sequence, so none is missed.

Why it is fast

There are 2ⁿ leaves and each costs up to n to copy the path, so the work is

about n · 2ⁿ

You cannot beat 2ⁿ, because that is how many teams must be written down. The pattern spends nothing beyond the output itself.

How to recognise it in an interview

Cues: "all subsets", "all combinations", "every way to choose", "power set", or a question where n is small (up to about 20) and each item is either used or not. The first thing to say: "each element is in or out, so I will backtrack with take-then-skip and copy the path at the leaves." Subsets is the example above. Subsets II has duplicates; sort first, and when skipping an element also skip its equal neighbours, so each distinct team is still made once. Partition Equal Subset Sum is the same in-or-out tree with a running sum, where pruning or a DP table replaces listing.

02The idea in one line

At each index choose to take it or not; the leaf is one subset.

Reach for it when: Subsets, subsets with duplicates, bitmask enumeration.

Cost: O(2^n) time.

03The walk-through, step by step

The video works one example: Subsets of [1,2,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. At each index: take it or skip it; every leaf is one subset
2. Index 0: take 1, push it on the path
3. Index 1: take 2, push it on the path
4. Index 2: take 3, push it on the path
5. Index 3 is past the end: record 123
6. Back at index 2: skip 3, pop it off
7. Index 3 is past the end: record 12
8. Back at index 1: skip 2, pop it off
9. Index 2: take 3, push it on the path
10. Index 3 is past the end: record 13
11. Back at index 2: skip 3, pop it off
12. Index 3 is past the end: record 1
13. Back at index 0: skip 1, pop it off
14. Index 1: take 2, push it on the path
15. Index 2: take 3, push it on the path
16. Index 3 is past the end: record 23
17. Back at index 2: skip 3, pop it off
18. Index 3 is past the end: record 2
19. Back at index 1: skip 2, pop it off
20. Index 2: take 3, push it on the path
21. Index 3 is past the end: record 3
22. Back at index 2: skip 3, pop it off
23. Index 3 is past the end: record ∅
24. 8 = 2³ subsets, each index decided twice down every branch
25. Exponential by nature: O(2^n · n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Backtracking: Permutations with a used set, Combination sum with a start index, Grid DFS with undo, Constraint placement with pruning, Generate valid sequences.