THE RECURSION TREE
YOUR CALL
A recursive function is a tree of calls: each call is a node, each choice an edge, and the call stack is just the path from the root to wherever you are now. Once you can see that tree (the base case at the leaves, the partial solution built on the way down, the backtrack that undoes each choice on the way up), subsets, combinations and permutations stop being separate tricks and become the same skeleton with different branches. Five patterns, eleven problems, each one animated as a growing tree beside its call stack and the results it emits.
This is not a list of problems. It is 5 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
11 PROBLEMS · EVERY ONE LINKS TO A JUDGE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Eleven problems, five branching rules. The cards are the phrases in a statement that pick the tree's shape for you, all subsets, all combinations, all orderings. Before you write a line.
one base case and one recursive call that returns a value you combine
PLAIN RECURSION (return & combine)O(depth) stackat every index branch two ways. Take it or leave it; 2ⁿ leaves
PICK / NOT-PICK binary treeO(2ⁿ · n)carry a remaining target, reuse or advance, and PRUNE on overshoot
N-ARY TREE + PRUNEO(2^T) worstlet the constraint decide which moves are legal; every leaf is valid
BUILD ALONG VALID MOVESO(Catalan · n)branch on each element not yet used; mark, recurse, unmark; n! leaves
USE-SET PERMUTATIONSO(n! · n)Backtracking is exponential, so the input bound tells you what is even feasible to enumerate. A permutation search is fine at n ≤ 12; subsets at n ≤ 20; past that the problem wants memoisation or a different idea entirely.
n IS TINY FOR A REASON · READ THE BOUND, THEN CHOOSE ENUMERATE vs DP
Five patterns. Return-&-combine is the warm-up; pick/not-pick is the archetype; prune, valid-moves and the use-set are the three flavours of backtracking. The hard backtracking (deck 2), grids and boards, composes these.
Every recursive function needs two things to terminate correctly. What are they?
A base case, and a recursive step that provably approaches it. The base case is the leaf where recursion stops and returns an answer directly; the recursive step must reduce the problem, a smaller n, a larger index, a shorter remaining target, so that every path reaches a base case. The classic bug is recursing on something that isn't strictly smaller (f(n) calling f(n), or forgetting to advance the index), which runs until the stack overflows. Before writing the body, name the base case and the thing that shrinks.
In subsets, you do cur.push_back(x); recurse(); cur.pop_back();. Why is the pop_back essential?
Because the partial solution is shared, not copied. One cur vector threads through the entire recursion to avoid copying at every node. When the “take x” subtree returns, x is still sitting in cur; if you don't pop_back it, the sibling branch, and everything above. Inherits a choice that was supposed to be local. That push-recurse-pop around the call is exactly what the word backtracking names: make a choice, explore it, then take it back.
AFTER THIS UNIT YOU CANlook at a recursive function and say how many children each call makes, and therefore whether its tree is a path or a bush.
Before backtracking, see the shape of recursion itself. A recursive call is a node in a tree: it may spawn children (more calls), and when it hits a base case it returns a value directly. The call stack is nothing more than the path from the root to the node running right now. Fast power is the purest example, a single path down (pow(x,n) waits on pow(x,n/2)) and the values combine on the way back up.
WHAT IS A RECURSIVE FUNCTION, REALLY, AND HOW DOES THE STACK RELATE TO THE TREE?
The call stack is exactly the root-to-current path. Its depth is the tree's depth, never its node count.
Depth and cost are the same thing: a deep recursion is an expensive one.
Every recursion you meet first. Factorial, sum-to-n, reverse a string. Has one child per call, and there depth really does equal the number of calls.
Depth is the stack; the node count is the work. Pow is log n deep and makes log n calls; Hanoi is n deep and makes 2ⁿ calls. The branching factor is what separates them.
Pow(x, n) by halving does half = pow(x, n/2) then returns half*half (even) or half*half*x (odd). Why is this O(log n) rather than O(n)?
The exponent halves every call, so the recursion is log n deep. Going n → n/2 → n/4 → … → 0 takes about log₂ n steps, and each step multiplies a constant number of times, so the total work is O(log n). The naive x·x·…·x loop is O(n) multiplies; halving the exponent is the same idea as binary search applied to exponentiation. The tree here is a single path. One child per node, which is why the depth alone bounds the cost.
Tower of Hanoi moves n disks with hanoi(n-1) ; move big disk ; hanoi(n-1). Run it for n = 4. How many moves?
2ⁿ − 1. The recurrence T(n) = 2·T(n−1) + 1 with T(0)=0 unrolls to 2ⁿ − 1: to move n disks you move the top n−1 aside, move the largest, then move the n−1 back, two subproblems of size n−1. Unlike fast power (one child), Hanoi has two children per node, so the tree is full and the move count is exponential. It is the cleanest illustration that the branching factor, not the depth, is what makes recursion explode.
This fast-power is wrong for odd n. Which line is the bug?
1 long pw(long x, long n) {
2 if (n == 0) return 1;
3 long half = pw(x, n / 2);
4 return half * half;
5 }
Line 4. n / 2 is integer division, so for odd n the two halves cover n − 1 factors and one x is lost. pw(2,3) returns pw(2,1)² = 4 instead of 8. The fix is the odd branch: return (n & 1) ? half*half*x : half*half;. Every line here compiles and the function returns a plausible number for every input, which is why this class of bug survives a quick test on n = 4.
A function computes the nth Fibonacci number as fib(n-1) + fib(n-2), with no memo. Which unit-1 idea tells you its cost without running it?
Count the children. Each call spawns two, so the node count roughly doubles per level and the tree is a bush: about φⁿ nodes. This is exactly the Pow-versus-Hanoi contrast. Pow makes one child and costs log n, Hanoi and Fibonacci make two and cost exponentially. The depth here is only n, which is why depth alone never tells you the cost.
Fast exponentiation is the simplest recursion tree, a single path, because each call has exactly one child. pow(x, n) waits on pow(x, n/2), which waits on pow(x, n/4) … until pow(x, 0) = 1 returns. Then every frame unwinds, squaring the result on the way up (and multiplying by x when its exponent was odd). The call stack pushing down and the values returning up are the two halves of every recursion, here with no branching to hide them, so O(log n) depth is the whole story.
“Compute x raised to n” where n can be large or negative. The multiply-in-a-loop answer is O(n); the tell for O(log n) is that x^n = (x^{n/2})², halve the exponent.
Compute half = x^{n/2} with one recursive call, then square it; if n is odd, multiply one more x in. Negative exponents flip to 1/x with n made positive. Each call halves n, so the depth, and the cost. Is log n.
// x^n = (x^(n/2))^2, times x once more if n is odd. Halving -> O(log n). double myPow(double x, long n) { if (n < 0) return 1.0 / myPow(x, -n); // x^-n = 1 / x^n (n is long) if (n == 0) return 1.0; // base case double half = myPow(x, n / 2); // ONE recursive call return (n % 2 == 0) ? half * half // even: square : half * half * x; // odd: square, then x }
// x^n = (x^(n/2))^2, times x once more if n is odd. Halving -> O(log n). public double myPow(double x, int n) { long e = n; // widen: -2^31 has no positive int if (e < 0) return 1.0 / pow(x, -e); // x^-n = 1 / x^n return pow(x, e); } private double pow(double x, long n) { if (n == 0) return 1.0; // base case double half = pow(x, n / 2); // ONE recursive call return (n % 2 == 0) ? half * half // even: square : half * half * x; // odd: square, then one more x }
# x^n = (x^(n/2))^2, times x once more if n is odd. def myPow(x, n): if n < 0: return 1.0 / myPow(x, -n) if n == 0: return 1.0 half = myPow(x, n // 2) return half * half if n % 2 == 0 else half * half * x
Negating INT_MIN and looping n times. n = -2³¹ can't be represented as a positive int, so widen n to long before -n. And resist the O(n) multiply loop, halving the exponent is the whole point, turning a 10⁹ exponent into ~30 multiplies.
“Count the good numbers of length n” where even indices need an even digit and odd indices a prime digit, answer mod 10⁹+7. Huge n plus a modulus screams modular fast power, not enumeration.
Even indices (0-based) have 5 choices {0,2,4,6,8}; odd indices have 4 primes {2,3,5,7}. The positions are independent, so the count is 5^{#even} · 4^{#odd}. For length n: #even = ⌈n/2⌉, #odd = ⌊n/2⌋. Both powers use the O(log n) fast-power under a modulus.
// Even slots: 5 choices; odd slots: 4 primes. Independent -> multiply. const long MOD = 1e9 + 7; long power(long b, long e) { // modular fast power, O(log e) long r = 1; b %= MOD; while (e > 0) { if (e & 1) r = r * b % MOD; // take modulus every multiply b = b * b % MOD; e >>= 1; } return r; } int countGoodNumbers(long n) { long even = (n + 1) / 2, odd = n / 2; // #even-index, #odd-index positions return (int)(power(5, even) * power(4, odd) % MOD); }
// Even slots: 5 choices; odd slots: 4 primes. Independent -> multiply. static final long MOD = 1_000_000_007L; long power(long b, long e) { // modular fast power, O(log e) long r = 1; b %= MOD; while (e > 0) { if ((e & 1) == 1) r = r * b % MOD; // take modulus every multiply b = b * b % MOD; e >>= 1; } return r; } public int countGoodNumbers(long n) { long even = (n + 1) / 2, odd = n / 2; // #even-index and #odd-index slots return (int) (power(5, even) * power(4, odd) % MOD); }
# Even slots: 5 choices; odd slots: 4 primes. Independent -> multiply. def countGoodNumbers(n): MOD = 10**9 + 7 even, odd = (n + 1) // 2, n // 2 return pow(5, even, MOD) * pow(4, odd, MOD) % MOD
Overflow, and miscounting the slots. b*b exceeds 32 bits, accumulate in long and reduce mod 1e9+7 after every multiply. And the split is ⌈n/2⌉ even-index slots vs ⌊n/2⌋ odd-index: index 0 counts as even, so an odd-length number has one more even slot than odd.
“Move n disks from one peg to another, one at a time, never a bigger disk on a smaller.” The recursive structure is explicit: it is the textbook divide-into-two-subproblems recursion.
To move n disks from from to to using aux: move the top n−1 to aux, move the largest disk to to, then move the n−1 from aux to to. Two subproblems of size n−1 around one real move. hence 2ⁿ − 1 moves.
// Move n-1 aside, move the big disk, move n-1 back. T(n)=2T(n-1)+1. void hanoi(int n, char from, char to, char aux) { if (n == 0) return; // base case: no disk to move hanoi(n - 1, from, aux, to); // park top n-1 on the aux peg cout << "move " << n << ": " << from << " -> " << to << "\n"; hanoi(n - 1, aux, to, from); // bring the n-1 back on top } // disks(n) = 2^n - 1 total moves
// Move n-1 aside, move the big disk, move n-1 back. T(n)=2T(n-1)+1. void hanoi(int n, char from, char to, char aux) { if (n == 0) return; // base case: no disk to move hanoi(n - 1, from, aux, to); // park top n-1 on the aux peg System.out.println("move " + n + ": " + from + " -> " + to); hanoi(n - 1, aux, to, from); // bring the n-1 back on top } // disks(n) = 2^n - 1 total moves, and that bound is tight
# Move n-1 aside, move the big disk, move n-1 back. def hanoi(n, frm, to, aux, moves): if n == 0: return hanoi(n - 1, frm, aux, to, moves) # park top n-1 on aux moves.append((frm, to)) # move disk n hanoi(n - 1, aux, to, frm, moves) # bring n-1 back return moves # len == 2**n - 1
Swapping the peg roles wrongly in the two calls. The auxiliary of the first call is the destination (to), and the second call moves from the aux to the target using the original source as its new aux. Get the three peg arguments in the wrong order and disks land on the wrong peg or a bigger disk sits on a smaller, trace n = 2 by hand to lock the pattern.
In one sentence. What does the branching factor of a recursion tell you that the depth does not?
Say it out loud, or type it. Nothing is graded, nothing is stored.
The depth tells you how much stack you need. The branching factor tells you how many nodes exist, and the running time follows from it. Pow branches once and costs log n; Hanoi branches twice and costs 2ⁿ−1, and both are only n deep.
A nearly-right answer says “more branching means more calls”. True, and it stops one step short: the word missing is usually depth. Until you name depth and node count as two different quantities, the sentence does not yet separate Pow from Hanoi.
Three items on a table, and you want every bag you could walk out with. Stand at item 0 holding an empty bag. You have one decision: leave it, or take it. Then item 1, same decision. Then item 2. Three yes/no choices, 2³ = 8 bags.
Here is the part that catches people. One bag, shared by the whole walk. Taking an item pushes it in; coming back pops it out, so the next branch starts from your parent's bag, not yours.
When that pop runs, whose bag are you putting back?
cur holds exactly the items you took on the path from the root to the node running now. Nothing else is ever in it.
Subsets can be written as pick/not-pick (recurse skip, then recurse take) OR as a for-loop that, at each node, records cur and tries each later index. What do these two shapes have in common?
Same tree, two equivalent traversals. Pick/not-pick is a strict binary tree that records a subset only at its 2ⁿ leaves. The for-loop form treats every node as a subset (it records on entry, then extends by each later element), which is the natural shape for Subsets II because the duplicate-skip lives in the loop. Both visit the same combinations; choosing between them is about where the recording and the dedup are most convenient, not about correctness.
Subsets II on [1, 2, 2] (sorted). The dedup rule is if (j > i && a[j] == a[j-1]) continue;. How many subsets?
6. With distinct elements you'd get 2³ = 8, but the two 2s are identical, so any subset that differs only in which 2 it picked is the same multiset. The rule j > i && a[j]==a[j-1] skips the second 2 at the same tree level. It forbids starting a fresh branch with a duplicate, while still allowing {2,2} to form by descending. The distinct subsets are {}, {1}, {2}, {1,2}, {2,2}, {1,2,2}.
This subsets records every leaf, but the answer comes back as 2ⁿ copies of the same vector. Which line is the bug?
1 void go(int i) {
2 if (i == n) { out.push_back(cur); return; }
3 go(i + 1);
4 cur.push_back(a[i]);
5 go(i + 1);
6 cur.pop_back();
7 }
Line 2, if out was declared to hold references or pointers. cur is one buffer reused by the entire tree (this unit's invariant), so storing anything but a copy means all 2ⁿ entries alias the same vector, and by the time the recursion unwinds that vector is empty. With vector<vector<int>> out the push_back copies and the code is correct; with vector<vector<int>&> or a vector of pointers it is not. This is the one bug in the deck that produces output of exactly the right shape and entirely the wrong content.
Delete line 6. The cur.pop_back(), and run subsets on [1, 2]. What comes out?
Later branches inherit choices that were never theirs. There is one cur and the whole tree shares it. The pop is not a discard. It is a restore, putting cur back to exactly what the parent was holding so the sibling branch starts where the parent did. Take that away and the take-branch's element is still sitting in cur when the recursion unwinds, so every node visited afterwards is standing in a bag it did not pack. Nothing was ever wrong and nothing was being thrown away; the pop is bookkeeping, and it is the whole of what ‘backtracking’ means here.
Six lines, and every one of them is doing one of three jobs. Name the job for each block before you read the reason. The point is to see the shape, not to memorise the lines.
2 if (i == n) { out.push_back(cur); return; }The leaf. i == n means every item has been decided, so cur is one complete answer, and it is copied out, not referenced, because the buffer is about to change again.
3 go(i + 1);
The whole of ‘leave it’. There is nothing to undo afterwards precisely because nothing was done: cur is untouched, so this branch inherits the bag exactly as the parent had it.
4 cur.push_back(a[i]); 5 go(i + 1); 6 cur.pop_back();
Three lines that must travel together. The push makes the claim, the call explores everything that follows from it, and the pop takes the claim back so the caller's next move starts from the caller's bag. Delete line 6 and every later branch inherits this one's choice.
The pick / not-pick tree is the archetype the rest of the deck varies. At each index you branch two ways. Leave the element out, or take it, so the tree is binary and every one of its 2ⁿ leaves is one subset. Taking an element pushes it onto the partial; returning from that branch pops it back off. That push/pop around the recursive call is backtracking: the partial is shared, so you must undo your choice on the way up or it leaks into the sibling branch.
0..2ⁿ-1 instead of by recursing.
“Return all subsets / the power set.” Distinct elements, every combination wanted. The archetypal pick / not-pick recursion, 2ⁿ subsets.
Walk an index. At each element recurse twice, once without it, once with it pushed onto the running subset, and when the index passes the end, record the current subset. The take-branch's push_back is undone by a pop_back after it returns.
// Pick / not-pick at each index; every leaf (i==n) is one subset. void solve(int i, vector<int>& nums, vector<int>& cur, vector<vector<int>>& res) { if (i == nums.size()) { res.push_back(cur); return; } // record a COPY solve(i + 1, nums, cur, res); // 1) SKIP nums[i] cur.push_back(nums[i]); // 2) TAKE nums[i] solve(i + 1, nums, cur, res); cur.pop_back(); // BACKTRACK } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; vector<int> cur; solve(0, nums, cur, res); return res; }
// Pick / not-pick at each index; every leaf (i==n) is one subset. void solve(int i, int[] nums, List<Integer> cur, List<List<Integer>> res) { if (i == nums.length) { res.add(new ArrayList<>(cur)); return; } // a COPY solve(i + 1, nums, cur, res); // 1) SKIP nums[i] cur.add(nums[i]); // 2) TAKE nums[i] solve(i + 1, nums, cur, res); cur.remove(cur.size() - 1); // undo: cur is SHARED } public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); solve(0, nums, new ArrayList<>(), res); return res; }
# Pick / not-pick at each index; every leaf is one subset. def subsets(nums): res, cur = [], [] def solve(i): if i == len(nums): res.append(cur[:]) # record a COPY return solve(i + 1) # skip nums[i] cur.append(nums[i]) # take nums[i] solve(i + 1) cur.pop() # backtrack solve(0) return res
Recording cur by reference and forgetting the pop_back. res.push_back(cur) must copy the vector; storing a reference makes every recorded subset alias the shared buffer and end up empty. And the pop_back after the take-branch is what stops the choice leaking into the skip-branch. Omit it and you get garbage.
“All subsets, but the input contains duplicates and the output must have no duplicate subsets.” The tell is: sort first, then skip duplicates at the same tree level.
Sort so equal values are adjacent. Use the loop form where every node is a subset: at each level try each later index as the next element, but skip a value equal to the previous one at this same level (j > i && a[j]==a[j-1]). That forbids two branches starting with the same value while still letting a value repeat by descending.
// Sort, then skip a duplicate value at the SAME tree level (j > i). void solve(int i, vector<int>& nums, vector<int>& cur, vector<vector<int>>& res) { res.push_back(cur); // every node is a subset for (int j = i; j < nums.size(); j++) { if (j > i && nums[j] == nums[j - 1]) continue; // dup at this level cur.push_back(nums[j]); solve(j + 1, nums, cur, res); // each element used once cur.pop_back(); // backtrack } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; vector<int> cur; solve(0, nums, cur, res); return res; }
// Sort, then skip a duplicate value at the SAME tree level (j > i). void solve(int i, int[] nums, List<Integer> cur, List<List<Integer>> res) { res.add(new ArrayList<>(cur)); // every node is a subset for (int j = i; j < nums.length; j++) { if (j > i && nums[j] == nums[j - 1]) continue; // dup at this level cur.add(nums[j]); solve(j + 1, nums, cur, res); // each element used at most once cur.remove(cur.size() - 1); } } public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // the skip needs equals adjacent List<List<Integer>> res = new ArrayList<>(); solve(0, nums, new ArrayList<>(), res); return res; }
# Sort, then skip a duplicate value at the SAME tree level (j > i). def subsetsWithDup(nums): nums.sort() res, cur = [], [] def solve(i): res.append(cur[:]) for j in range(i, len(nums)): if j > i and nums[j] == nums[j - 1]: continue # skip dup at this level cur.append(nums[j]) solve(j + 1) cur.pop() solve(0) return res
Dropping the j > i in the skip condition. Skipping whenever nums[j]==nums[j-1] also blocks the legitimate descent that builds {2,2}, losing valid subsets. The guard must be “this is not the first choice at this level”. j > i, so duplicates are refused only as fresh sibling branches, never as deeper picks. And the sort is mandatory; without it duplicates aren't adjacent and the rule does nothing.
Two statements, and the same binary tree underneath both. What separates them is whether anything has to be carried down the tree.
Count how many binary strings of length n contain no two adjacent 1s.
You branch two ways at every position, so the tree looks like subsets, but you only need the count. Each call returns a number and the parent adds them. Nothing is carried down, so there is no shared buffer and nothing to pop.
Print every string you can build by deleting any combination of characters from a word.
The same two-way branch, but now each leaf must be reported, so the characters kept so far live in one shared partial. That buffer is what forces push → recurse → pop.
A rod of length n has a price for each cut length. Find the greatest revenue you can get by cutting it.
The answer is one number, not a list of cuts, so each call returns its best revenue and the parent takes the max. You never need to know which cuts produced it, so nothing is carried down and nothing is undone.
AFTER THIS UNIT YOU CANtell reuse (recurse on i) from advance (recurse on i+1), and cut a branch before exploring it.
Combination Sum turns the binary tree n-ary and adds pruning. The move that makes backtracking fast. Carry a remaining target. Taking a candidate subtracts it from remaining, and because a value may be reused you can stay at the same index. Two things end a branch: remaining == 0 emits a combination, and remaining < 0 means you overshot. The entire subtree is dead and is cut without being explored.
HOW DO YOU ENUMERATE COMBINATIONS WITH A TARGET, AND CUT THE BRANCHES THAT CAN'T WIN?
remaining is the target minus the sum of every element on the current path. It never rises.
Recursing on i again risks infinite recursion. The index has to move or the call never bottoms out.
Every recursion you have written so far advances the index, so the index is the thing you have been taught guarantees termination.
The index is not the only measure that shrinks. remaining drops by at least the smallest candidate on every take, so the depth is bounded by target / min(candidates), a different ruler, still shrinking.
In Combination Sum (values reusable), the 'take' branch recurses on index i again, solve(i, rem - C[i]), not i+1. Why doesn't this loop forever?
Staying at i still shrinks remaining. Reuse is allowed, so the index doesn't advance on a take, but every candidate is positive, so remaining drops by at least 1 each time. That guarantees the branch reaches remaining == 0 (emit) or remaining < 0 (prune) in a bounded number of steps. The rule for termination isn't “the index must advance”. It's “some measure must strictly approach the base case,” and here that measure is remaining.
Combination Sum II on [1,1,2], target 3, using sort + if(j>i && a[j]==a[j-1]) continue; and recursing j+1. Which combinations come out?
Just {1,2}, once. Sorted input is [1,1,2] and each element is used at most once (recurse j+1). The only subset summing to 3 is {1,2}. 1+1=2 can't reach 3 with no third 1, and {1,1,2}=4 overshoots. Without dedup you'd emit {1,2} twice (starting from either 1); the guard j > i && a[j]==a[j-1] skips the second 1 as a fresh branch at the top level, so it appears exactly once. Using each element once plus level-dedup is the whole difference from Combination Sum I.
Combination Sum turns the binary tree n-ary and adds the move that makes backtracking fast: pruning. Carry a remaining target; taking a candidate subtracts it (and you may take the same candidate again, so the branch stays at index i). Two things end a branch, remaining == 0 emits a combination, and remaining < 0 means you overshot, so the entire subtree is dead and is cut without exploring it. Recognising a branch can never succeed and abandoning it early is what separates backtracking from brute force.
“All unique combinations summing to a target, and a number may be reused unlimited times.” The reuse is the signal, recurse on the same index after taking a candidate.
Carry a remaining target. At index i either take C[i] (subtract it and stay at i, since reuse is allowed) or skip to i+1. remaining == 0 records a combination; remaining < 0 or running out of candidates prunes the branch.
// Take C[i] (stay at i to reuse) or skip to i+1. rem hits 0 -> emit. void solve(int i, int rem, vector<int>& C, vector<int>& cur, vector<vector<int>>& res) { if (rem == 0) { res.push_back(cur); return; } // exact hit if (i == C.size() || rem < 0) return; // out / overshoot -> prune cur.push_back(C[i]); solve(i, rem - C[i], C, cur, res); // REUSE C[i]: stay at i cur.pop_back(); solve(i + 1, rem, C, cur, res); // move on to the next candidate } vector<vector<int>> combinationSum(vector<int>& C, int t) { vector<vector<int>> res; vector<int> cur; solve(0, t, C, cur, res); return res; }
// Take C[i] (stay at i to reuse) or skip to i+1. rem hits 0 -> emit. void solve(int i, int rem, int[] C, List<Integer> cur, List<List<Integer>> res) { if (rem == 0) { res.add(new ArrayList<>(cur)); return; } // exact hit if (i == C.length || rem < 0) return; // out / overshoot -> prune cur.add(C[i]); solve(i, rem - C[i], C, cur, res); // REUSE C[i]: stay at i cur.remove(cur.size() - 1); solve(i + 1, rem, C, cur, res); // or move past it for good }
# Take C[i] (stay at i to reuse) or skip to i+1. rem hits 0 -> emit. def combinationSum(C, target): res, cur = [], [] def solve(i, rem): if rem == 0: res.append(cur[:]); return if i == len(C) or rem < 0: return cur.append(C[i]) solve(i, rem - C[i]) # reuse C[i] cur.pop() solve(i + 1, rem) # move on solve(0, target) return res
Advancing the index on the take branch. Reuse means the take must recurse on i, not i+1; using i+1 silently solves the “each used once” problem instead. Termination still holds because remaining strictly drops. Also prune with rem < 0 at entry, not only at a leaf, or you generate whole doomed subtrees.
“Combinations summing to a target, each number used at most once, and the candidate list has duplicates, no duplicate combinations in the output.” Sort + level-dedup + advance the index.
Sort the candidates. Use the loop form: at each level try each later index, skipping a value equal to the previous at this level (j > i). Each pick recurses on j+1 (used once). On sorted input, break the moment C[j] > remaining. Every later candidate is even larger.
// Sort; use each once (j+1); skip dup at this level; break when C[j] > rem. void solve(int i, int rem, vector<int>& C, vector<int>& cur, vector<vector<int>>& res) { if (rem == 0) { res.push_back(cur); return; } for (int j = i; j < C.size(); j++) { if (j > i && C[j] == C[j - 1]) continue; // skip dup at this level if (C[j] > rem) break; // sorted -> prune the rest cur.push_back(C[j]); solve(j + 1, rem - C[j], C, cur, res); // each element once cur.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& C, int t) { sort(C.begin(), C.end()); vector<vector<int>> res; vector<int> cur; solve(0, t, C, cur, res); return res; }
// Sort; use each once (j+1); skip dup at this level; break when C[j] > rem. void solve(int i, int rem, int[] C, List<Integer> cur, List<List<Integer>> res) { if (rem == 0) { res.add(new ArrayList<>(cur)); return; } for (int j = i; j < C.length; j++) { if (j > i && C[j] == C[j - 1]) continue; // skip dup at this level if (C[j] > rem) break; // sorted -> prune the rest cur.add(C[j]); solve(j + 1, rem - C[j], C, cur, res); // j+1: each used once cur.remove(cur.size() - 1); } }
# Sort; use each once (j+1); skip dup at this level; break when C[j] > rem. def combinationSum2(C, target): C.sort() res, cur = [], [] def solve(i, rem): if rem == 0: res.append(cur[:]); return for j in range(i, len(C)): if j > i and C[j] == C[j - 1]: continue # skip dup at this level if C[j] > rem: break # sorted -> prune cur.append(C[j]) solve(j + 1, rem - C[j]) cur.pop() solve(0, target) return res
Confusing this with Combination Sum I. Here each element is used once, so the take must recurse on j+1, and duplicates in the input force the sort-and-skip. The dedup guard is again j > i (same level only), and the break on C[j] > rem depends on the array being sorted, so the sort is doing double duty.
“Combinations of exactly k numbers from 1..9 (each once) summing to n.” A fixed count plus a small fixed pool, a bounded backtracking with two prune conditions.
Recurse choosing strictly increasing digits from a start value. A branch is a solution when it has k digits and remaining == 0. Prune hard: stop a branch once it has k digits, and (digits ascending) break as soon as d > remaining.
// Exactly k strictly-increasing digits from 1..9 summing to rem. void solve(int start, int k, int rem, vector<int>& cur, vector<vector<int>>& res) { if (cur.size() == k) { // fixed count reached if (rem == 0) res.push_back(cur); // ...and it sums exactly return; } for (int d = start; d <= 9; d++) { if (d > rem) break; // ascending -> the rest overshoot cur.push_back(d); solve(d + 1, k, rem - d, cur, res); // strictly increasing cur.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; vector<int> cur; solve(1, k, n, cur, res); return res; }
// Exactly k strictly-increasing digits from 1..9 summing to rem. void solve(int start, int k, int rem, List<Integer> cur, List<List<Integer>> res) { if (cur.size() == k) { // fixed count reached if (rem == 0) res.add(new ArrayList<>(cur)); // ...and it sums exactly return; } for (int d = start; d <= 9; d++) { if (d > rem) break; // ascending -> the rest overshoot too cur.add(d); solve(d + 1, k, rem - d, cur, res); // d+1 keeps it strictly increasing cur.remove(cur.size() - 1); } }
# Exactly k strictly-increasing digits from 1..9 summing to rem. def combinationSum3(k, n): res, cur = [], [] def solve(start, rem): if len(cur) == k: if rem == 0: res.append(cur[:]) return for d in range(start, 10): if d > rem: break # ascending -> prune cur.append(d) solve(d + 1, rem - d) # strictly increasing cur.pop() solve(1, n) return res
Checking the sum but not the count (or vice-versa). A valid answer needs both cur.size() == k and rem == 0; test the count first and only accept when the remaining is also zero. Recursing on d+1 (not d) is what enforces distinct, strictly increasing digits. Reuse would produce {1,1,…}, which this problem forbids.
Three techniques on the board now. The question is what shrinks as you descend, the index, or a budget.
From stick lengths, list every multiset summing to exactly L, where a length may be used as often as you like.
“As often as you like” is the tell: taking a stick leaves the same index available, so you recurse on i and let the remaining budget shrink instead. Overshoot kills the whole subtree without exploring it.
Given n distinct coins, list every subset whose values are all even.
Each coin is used at most once and the index always advances, so this is the plain in-or-out tree. The even test only decides which leaves you keep. It never changes the shape.
How many distinct paths are there from the top-left to the bottom-right of a grid, moving only right or down?
Two choices at every cell, so the tree branches, but the answer is a count. Each call returns a number and the parent adds the two. No path is ever written down, so there is no partial and no pop.
AFTER THIS UNIT YOU CANpush the constraint into the choice so no invalid string is ever built, instead of generating everything and filtering at the end.
Now the constraint shapes the tree. Instead of generating everything and filtering, take only the moves the rule permits, so every leaf is already valid. Generate Parentheses builds a string one bracket at a time: add '(' only while open < n, add ')' only while close < open. Letter Combinations is the same idea over a mapping, at each digit, branch over exactly that digit's letters.
HOW DO YOU GENERATE ONLY THE VALID SEQUENCES. WITHOUT A VALIDITY CHECK AT THE END?
At every node close ≤ open ≤ n. The prefix built so far is a valid prefix of some balanced string.
You generate all 2ⁿ strings and keep the balanced ones. The constraint is a filter you apply at the leaves.
It is the obvious brute force, and it does produce exactly the right answer.
Move the constraint into the branch. Never add ) while close == open and no invalid string is ever constructed. The tree itself shrinks from 4ⁿ to the Catalan number, rather than being filtered after the fact.
Generate Parentheses adds ')' only when close < open. What would go wrong if you added it whenever close < n instead?
You'd build unbalanced strings. close < open guarantees you never write a ')' that has no unmatched '(' to close, so at every step the prefix is valid and every leaf is a well-formed string. Relaxing it to close < n lets ')' get ahead of '(' and produces junk like “)(” that you'd then have to filter out. The point of this pattern is that the guard replaces the filter. Invalid strings are never generated in the first place.
Letter Combinations of "23" (2→abc, 3→def). How many leaves does the recursion tree have?
9 leaves. Digit '2' offers {a,b,c} and '3' offers {d,e,f}, so the tree branches 3 ways at the first level and 3 ways under each of those, giving 3 × 3 = 9 length-2 strings (ad, ae, af, bd, …, cf). In general the leaf count is the product of the branch counts, ∏ |MAP[digit]|, the same multiplicative structure as permutations, just with a fixed per-level branching given by the keypad.
Generate Parentheses builds a string one bracket at a time, but the constraint is baked into which moves are even allowed: add '(' only while open < n, add ')' only while close < open. Because an invalid move is never taken, the tree contains only well-formed strings. Every leaf is already balanced, no validity check needed at the end. It is the cleanest example of backtracking's real idea: don't generate everything and filter; shape the tree so the wrong answers can't grow.
“Generate all well-formed parentheses of n pairs.” “Well-formed” is the tell: don't generate all 2^{2n} strings and filter. Build only along valid moves.
Track open and close counts. You may add '(' while open < n, and ')' while close < open. Because ')' can never overtake '(', the running prefix is always valid and every length-2n leaf is a balanced string, no final check needed.
) than ( can never be repaired, so it need never be built. Constraining the branch turns 4ⁿ into the Catalan number. The filter becomes the choice.→// Add '(' while open<n, ')' while close<open. Every leaf is valid. void gen(int open, int close, int n, string& cur, vector<string>& res) { if ((int)cur.size() == 2 * n) { res.push_back(cur); return; } if (open < n) { cur += '('; gen(open + 1, close, n, cur, res); cur.pop_back(); } if (close < open) { cur += ')'; gen(open, close + 1, n, cur, res); cur.pop_back(); } } vector<string> generateParenthesis(int n) { vector<string> res; string cur; gen(0, 0, n, cur, res); return res; }
// Add '(' while open<n, ')' while close<open. Every leaf is valid. void gen(int open, int close, int n, StringBuilder cur, List<String> res) { if (cur.length() == 2 * n) { res.add(cur.toString()); return; } if (open < n) { cur.append('('); gen(open + 1, close, n, cur, res); cur.deleteCharAt(cur.length() - 1); } if (close < open) { // the guard IS the prune cur.append(')'); gen(open, close + 1, n, cur, res); cur.deleteCharAt(cur.length() - 1); } }
# Add '(' while open<n, ')' while close<open. Every leaf is valid. def generateParenthesis(n): res, cur = [], [] def gen(op, cl): if len(cur) == 2 * n: res.append(''.join(cur)); return if op < n: cur.append('('); gen(op + 1, cl); cur.pop() if cl < op: cur.append(')'); gen(op, cl + 1); cur.pop() gen(0, 0) return res
Guarding ')' with close < n instead of close < open. The correct guard keeps every prefix balanced, so leaves need no validation; the wrong one generates malformed strings like “)(” that you'd have to filter. The whole pattern is that the constraint is the prune, never generate the invalid branch in the first place.
“All letter combinations a phone number could spell.” Each digit maps to a fixed set of letters and you want the Cartesian product, recurse over one digit's letters per level.
Keep the digit→letters keypad map. At digit index i, loop over that digit's letters; for each, append it and recurse on i+1. When i reaches the end, record the assembled string. The branching factor at each level is 3 or 4 (the keypad), so the leaf count is the product across digits.
// Branch over each digit's letters; a full-length leaf is one combination. const string MAP[] = {"","","abc","def","ghi","jkl", "mno","pqrs","tuv","wxyz"}; void solve(int i, string& digits, string& cur, vector<string>& res) { if (i == digits.size()) { if (!cur.empty()) res.push_back(cur); return; } for (char c : MAP[digits[i] - '0']) { // this digit's letters cur.push_back(c); solve(i + 1, digits, cur, res); cur.pop_back(); // backtrack } } vector<string> letterCombinations(string digits) { vector<string> res; string cur; if (!digits.empty()) solve(0, digits, cur, res); return res; }
// Branch over each digit's letters; a full-length leaf is one combination. static final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void solve(int i, String digits, StringBuilder cur, List<String> res) { if (i == digits.length()) { if (cur.length() > 0) res.add(cur.toString()); return; } for (char c : MAP[digits.charAt(i) - '0'].toCharArray()) { // this digit cur.append(c); solve(i + 1, digits, cur, res); cur.deleteCharAt(cur.length() - 1); } }
# Branch over each digit's letters; a full-length leaf is one combination. def letterCombinations(digits): if not digits: return [] MAP = {'2':'abc','3':'def','4':'ghi','5':'jkl', '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} res, cur = [], [] def solve(i): if i == len(digits): res.append(''.join(cur)); return for c in MAP[digits[i]]: cur.append(c); solve(i + 1); cur.pop() solve(0) return res
Returning [""] for an empty input. The empty digit string should yield an empty list, not a list containing the empty string. Guard it before recursing. The structure is otherwise identical to the other backtracks: the keypad just fixes each level's branching, so this is “permutations with a per-level alphabet.”
Four now. The split that matters: do you build only legal partials, or build freely and test at the leaf?
Fill a 9×9 grid so every row, column and 3×3 box holds 1–9 exactly once.
A digit goes down only on a square where it is currently legal, so no illegal board is ever built. The constraint lives in the choice, which is what makes it the same shape as generating balanced parentheses.
Given a target and coins usable at most once each, list every combination reaching it.
“At most once” is the discriminator against prune & reuse: the index advances after every take, so it is the ordinary in-or-out tree with a running sum.
Count the structurally distinct binary search trees you can build from n numbered nodes.
Pick a root, and the left and right subtrees are the same question on smaller counts. Each call hands back a number, the parent multiplies the two sides and sums over every root. Nothing is built, so there is nothing to unbuild.
AFTER THIS UNIT YOU CANbranch on which element goes here rather than on whether to take this one, and say why that swap forces a used-set.
Permutations arrange all the elements, so pick/not-pick no longer fits. You must branch on every element not yet used. A used array marks what the current partial already contains; each level chooses one remaining element, marks it, recurses, then unmarks it on the way back. With n choices at the root, n−1 at the next level, and so on, the tree has n! leaves, one per ordering.
HOW DO YOU GENERATE ALL n! ORDERINGS, AND WHAT ROLE DOES THE used SET PLAY?
used marks exactly the elements sitting in cur. The two never disagree.
Permutations are just subsets where you happen to keep all n elements.
Both walk the same array and both build a list, and the leaf of a full take-everything subsets path really does contain all n elements.
Subsets branch on a question about one index. Take it or not, 2 children, and i alone stops you revisiting. Permutations branch on which of the remaining elements goes next, n−depth children, so order matters and an index cannot say what is still available. The used-set does.
The permutations recursion does used[k]=true; push; recurse; used[k]=false; pop;. Both a used[k]=false AND a pop_back appear on the way back. Why two undos?
They reset two independent things. cur holds the order built so far, and used records which elements are spoken for; a choice mutated both, so backtracking must undo both. pop_back removes k from the current arrangement; used[k]=false returns it to the pool so a sibling branch can place it in a different position. Forget the used[k]=false and each element is usable only once ever, collapsing the output to a single permutation; forget the pop_back and the partial grows without bound.
Permutations of [1,2,3] gives 3! = 6 orderings. If instead you wanted permutations of a list with duplicates (e.g. [1,1,2]) without repeats, which technique from THIS deck transfers?
The sort-and-skip-duplicates-at-a-level trick. Permutations II is Permutations plus the exact dedup idea from Subsets II and Combination Sum II: sort the input, and at each tree level don't start two branches with the same value (skip nums[k] if nums[k]==nums[k-1] and nums[k-1] wasn't used in this path). It's the clearest sign the deck is a small set of composable moves. The used-set arranges, and the level-dedup you already learned removes the repeats.
Permutations arrange all the elements, so instead of pick/skip you branch on every element not yet used. A used set marks what the current partial already contains; each level chooses one of the remaining elements, marks it, recurses, then unmarks it on the way back. With n choices at the root, n−1 below, and so on, the tree has n! leaves. The used-set plus its symmetric undo is the permutation-specific flavour of the same backtracking skeleton.
“Return all orderings / permutations of distinct numbers.” Arranging every element (not choosing a subset) is the use-set recursion, n! results.
At each level, try every element not yet used: mark it used, push it onto the partial, recurse, then unmark and pop. A leaf is reached when the partial has all n elements. The used array is what stops an element appearing twice in one ordering.
// Branch on each unused element; mark, recurse, unmark. n! leaves. void solve(vector<int>& nums, vector<bool>& used, vector<int>& cur, vector<vector<int>>& res) { if (cur.size() == nums.size()) { res.push_back(cur); return; } for (int k = 0; k < nums.size(); k++) { if (used[k]) continue; // already in this permutation used[k] = true; cur.push_back(nums[k]); solve(nums, used, cur, res); used[k] = false; cur.pop_back(); // BACKTRACK: undo both } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> cur; vector<bool> used(nums.size(), false); solve(nums, used, cur, res); return res; }
// Branch on each unused element; mark, recurse, unmark. n! leaves. void solve(int[] nums, boolean[] used, List<Integer> cur, List<List<Integer>> res) { if (cur.size() == nums.length) { res.add(new ArrayList<>(cur)); return; } for (int k = 0; k < nums.length; k++) { if (used[k]) continue; // already in this permutation used[k] = true; cur.add(nums[k]); solve(nums, used, cur, res); cur.remove(cur.size() - 1); // undo BOTH pieces of state used[k] = false; } }
# Branch on each unused element; mark, recurse, unmark. n! leaves. def permute(nums): res, cur = [], [] used = [False] * len(nums) def solve(): if len(cur) == len(nums): res.append(cur[:]); return for k in range(len(nums)): if used[k]: continue used[k] = True; cur.append(nums[k]) solve() used[k] = False; cur.pop() # backtrack: undo both solve() return res
Undoing only one of the two state changes. A choice sets used[k]=true AND pushes onto cur, so the backtrack must reset both. Forget used[k]=false and each value is usable once ever, collapsing the output to a single permutation; forget pop_back and the partial never shrinks. The swap-based variant avoids the used array but the mark/unmark form is clearer and generalises to Permutations II.
In one sentence. What decides whether a problem needs a used set or just an index?
Say it out loud, or type it. Nothing is graded, nothing is stored.
Whether order matters. If the question is “is this element in?” an index is enough, because each element is offered once and never revisited. If the question is “which element goes here?” every remaining element is a candidate at every position, so you must track which are still available.
A nearly-right answer says “permutations need used, subsets do not”. The fact is stated, not the reason, and the reason is what transfers to a problem neither word appears in.
Subsets branches pick/not-pick (2 children); Permutations branches on each unused element (n children); Combination Sum reuses a candidate (stay at the same index). What single mental model unifies all three?
One recursion tree; only the branching rule changes. Every backtracking problem is the same skeleton. A node makes a choice, recurses on each option, and undoes the choice on the way back, and the problems differ only in what choices exist at a node (two, for pick/not-pick; n, for permutations; take-again-or-advance, for combination sum) and what makes a node a leaf (index past the end, target hit, length reached). Seeing the tree first, then filling in the branches, is why these stop being separate tricks.
What is the difference between pruning and just letting a branch reach a dead leaf, and why does it matter for backtracking's speed?
Pruning skips whole subtrees a brute force would still build. If you know a branch is doomed, remaining already went negative, or you're about to place a duplicate at the same tree level and produce a combination you've already emitted. You return immediately instead of recursing into it. Because a cut near the root removes an exponential number of descendants, pruning is not a micro-optimisation; it is the difference between backtracking and generating every candidate and filtering. The art of these problems is spotting the earliest moment a branch is provably dead.
Three statements from problems this deck never solves. The tree shape is decided by the statement, before you write a line.
Count the ways to climb n stairs taking 1 or 2 at a time.
One value comes back from each call and they add. No partial is carried down, so nothing needs undoing. That is return-and-combine, not backtracking.
For each element, decide in or out so the chosen ones hit a target sum.
A binary question about one index, asked n times. That is pick / not-pick; the target only decides which leaves you keep.
List every way to cut a string into pieces that are all palindromes.
You cut only where the piece so far is a palindrome, so no invalid split is ever built. Constraint in the choice, not a filter at the leaf.
Three more. If the first slide felt like guessing, the reason line is the part to read. It names the feature that decides, not the answer.
All ways to make change for X from an unlimited supply of coins.
Unlimited means the same coin index is still available after taking it, recurse on i, not i+1, and let the remaining amount be what shrinks.
Every distinct ordering of the letters of a word that contains repeats.
Order matters, so you choose which letter goes here rather than whether to take one. That needs a used-set. The repeats then need unit 2's sort-and-skip on top.
Place n queens on an n×n board so none attack.
A queen is placed only on a square no earlier queen attacks, so every partial board is legal. Same shape as generating parentheses, different legality test.
Backtracking bugs pass the sample and fail the rest: a missing pop_back, a wrong dedup guard, a prune that fires too late. Every one compiles and returns a believable answer.
The partial cur is shared across the whole tree. Push a choice, recurse, and if you don't pop_back after, the choice leaks into the sibling branch and every subset / combination downstream is wrong. The push and the pop must bracket the recursive call exactly.
If the recursive call isn't on a strictly smaller problem, a bigger index, a smaller n or remaining, no path reaches the base case and the stack overflows. In Combination Sum the reuse call stays at index i, but remaining still drops, so it terminates.
Subsets II and Combination Sum II need the input sorted, then if (j > i && a[j] == a[j-1]) continue; to skip a duplicate at the same tree level only. Skipping whenever a[j]==a[j-1] (ignoring j > i) wrongly drops valid combinations that legitimately repeat a value.
Checking remaining < 0 only at a leaf still generates the whole doomed subtree. Prune at entry (return the instant remaining < 0), and on sorted input break as soon as a candidate exceeds remaining. Every later one is bigger.
Fast power on an int overflows. Accumulate in long and take the modulus every multiply for Count Good Numbers. And Pow(x, n) with n = INT_MIN can't be negated in int; widen n to long before -n.
When you emit a solution you must store a copy of the partial (res.push_back(cur) copies the vector). If you stored a pointer/reference to the shared cur, every later pop_back would mutate the answer you already saved. You'd end with a list of identical empty vectors.
Eleven problems, eleven one-liners. The right-hand column is the branching rule. The shape of the tree that should come to mind the instant you read the statement.
Return-and-combine, pick/not-pick, prune-and-reuse, valid-moves-only, and the use-set. the vocabulary of recursion up to the hards ends there. Every one is push a choice, recurse, pop it back; the problems differ only in what choices a node offers and when a branch is a leaf. Deck 2 puts these on grids and boards (N-Queens, Sudoku, Word Search).
No lecture playlist was supplied, so this deck is problems, drills and visualisers, no concept videos. Problems are LeetCode except Tower of Hanoi (GeeksforGeeks). The hard backtracking problems are deck 2.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.