HANDS-ON · 90 minutes
Permutations, combinations, subsets, and grid search — built from one template and pruned down to practical speed.
I first ran into this pattern building a task-routing classifier for my orchestration framework: given a set of available agents and a queue of tasks, which assignment satisfies the most constraints? The brute-force answer is backtracking — try each assignment, undo it if it violates a constraint, move to the next. When I first worked through it, the undo step didn't feel natural. I kept thinking about adding choices, not reversing them. That's the step most people forget under time pressure, and it's what makes backtracking different from plain recursion.
Backtracking problems look different on the surface — generate all permutations, find all subsets, search a grid for a word — but they share one underlying shape: you build a candidate solution incrementally, and when you hit a dead end you undo the last choice and try the next option. The classic version strips away the domain and gives you the combinatorics directly.
The template is always the same:
Every variation — permutations, combinations, subsets, word search — is a different definition of choices(start) and base_case. The structure never changes.
Generate all combinations of size K from [1..N]. Order does not matter, so [1,2] and [2,1] are the same. Enforce this by only looking at elements from start onward.
The pruning condition n - (k - len(path)) + 2 is the key optimization. If you still need 2 more elements but only 1 remains, skip this branch entirely.
Generate all permutations of distinct integers. Order matters — [1,2] and [2,1] are different. Any unused element can go at each position; track what is in the current path with a used array.
graph TD R["start: []"] A["[1]"] B["[2]"] C["[3]"] A1["[1,2]"] A2["[1,3]"] B1["[2,1]"] B2["[2,3]"] C1["[3,1]"] C2["[3,2]"] R --> A --> A1 --> L1["[1,2,3]"] A --> A2 --> L2["[1,3,2]"] R --> B --> B1 --> L3["[2,1,3]"] B --> B2 --> L4["[2,3,1]"] R --> C --> C1 --> L5["[3,1,2]"] C --> C2 --> L6["[3,2,1]"] style L1 fill:#4ade80 style L2 fill:#4ade80 style L3 fill:#4ade80 style L4 fill:#4ade80 style L5 fill:#4ade80 style L6 fill:#4ade80
Each node is a choice; each green leaf is a completed permutation. Depth = N = 3. Total leaves = N! = 6.
At each element, you have exactly two choices: include it or skip it. Collect the path at every node, not just the leaves — that is the difference from combinations.
When this bites: if nums contains duplicates and the problem asks for unique subsets, sort nums first and skip duplicate elements at the same recursion level: if i > start and nums[i] == nums[i-1]: continue. Without this guard, you generate identical subsets from different starting positions.
Word Search is the canonical grid-backtracking problem: given a 2D board and a target word, does the word exist as a connected path (no cell reused)?
The backtracking structure: pick a starting cell matching word[0], then recursively try all four neighbors for word[1], and so on. Mark each cell visited before recursing; unmark on the way back.
Analogy — the corn maze: you enter a corn maze and pick a direction at each junction. If you hit a dead end, you retrace to the last junction and try the next direction. Marking cells prevents walking in circles. Restoring the mark when you leave means a different path — entering from a different direction — can still use that cell.
Close the code and try these from memory:
Reflective prompt: Backtracking enumerates all candidates; DP counts or optimizes over them. A problem asks for "all combinations summing to target." Another asks for the "number of ways to reach a target sum." For N=20 and T=100, which technique would you use for each, and why? Think about whether you need the actual paths, just a count, or an optimum.
Application-level questions on the backtracking template and its variants
1. What is the essential step that makes backtracking different from plain recursion?
Correct Answer: B
Backtracking explores candidates by adding a choice, recursing, then undoing (popping) that choice before the next iteration. Without the undo step, you are doing plain recursion and the path accumulates incorrectly.
2. In a combinations backtracking function, the recursive call uses 'start + 1' as the next start index. In a permutations function, you use a 'used' set instead. Why?
Correct Answer: C
Combinations avoid duplicates by only looking forward (start index). Permutations must consider every unused element at each position — [1,2] and [2,1] are different permutations. A 'used' set tracks which elements are currently in the path.
3. How many subsets does a set of N distinct elements have, and why?
Correct Answer: C
Each element has exactly two choices: in or out. With N independent binary choices, the total is 2^N. This is also the runtime of any algorithm that enumerates all subsets without pruning.
4. You are generating all combinations of size K from [1..N]. When should you prune a branch early?
Correct Answer: B
If you need k - len(path) more elements and there are fewer remaining (n - start + 1 < k - len(path)), no valid combination can be formed from this branch. Pruning here cuts large swaths of the search tree.
5. In word search on a 2D grid, you mark a cell as visited before recursing and unmark it after. Why is unmark necessary?
Correct Answer: B
Marking prevents visiting the same cell twice within one path (backtracking along the current path). But a different path that does not pass through this cell IS allowed to use it. Unmarking on backtrack restores that possibility.
6. A problem asks: 'Find ALL valid combinations that sum to a target.' Another asks: 'Find the NUMBER of valid combinations.' Which technique fits each?
Correct Answer: C
When you need to enumerate every solution, backtracking is the right tool — you build each candidate explicitly. When you only need a count or an optimum, DP is usually better because it avoids enumerating solutions and instead accumulates answers bottom-up.
7. A backtracking function generates all permutations of N elements. The maximum recursion depth is:
Correct Answer: C
At each level of recursion, one element is fixed in the current path. After N levels, the path is complete. Maximum depth = N. The total number of leaf nodes is N!, but the depth of any path from root to leaf is exactly N.
Problem: Given candidates (distinct positive integers) and a target, return all unique combinations that sum to target. The same number may be used multiple times.
Hint 1: Use the standard backtracking template. Since elements can be reused, pass i (not i+1) as the next start index in the recursive call.
Hint 2: Sort candidates first so you can break early when c > remaining. This prunes entire branches without inspecting each element.