Backtracking — Choose / Explore / Un-choose, with Pruning

Systematically trying every option — and undoing

Permutations, subsets, combinations, N-Queens, Sudoku: explore a decision tree, and on a dead end or after recording a result, undo the last choice and try the next. The template is always the same three moves: choose → explore (recurse) → un-choose.

The template

void backtrack(State path, Choices remaining) {
    if (isComplete(path)) { results.add(copyOf(path)); return; }   // copy! path is mutated
    for (Choice c : remaining) {
        if (!valid(c, path)) continue;        // PRUNE early — the whole point
        path.add(c);                          // choose
        backtrack(path, without(remaining, c)); // explore
        path.remove(path.size() - 1);         // un-choose (backtrack)
    }
}

Combinations C(3,2) from [1,2,3], traced

The diagram above is the combinations tree: pick k=2 of n=3 elements, passing a start index (0-based) so you never go backwards. Walk it with the template:

[]        choose 1 → [1]
[1]         choose 2 → [1,2]  complete: record copy, un-choose 2
[1]         choose 3 → [1,3]  complete: record copy, un-choose 3
[]        un-choose 1, choose 2 → [2]
[2]         choose 3 → [2,3]  complete: record copy, un-choose 3
[]        un-choose 2 — next start index is 2 (element 3):
          PRUNE: start > n−k  (2 > 3−2), i.e. even taking
          everything left, [3] can't reach size 2. Done: [1,2],[1,3],[2,3].

(The prune test start > n−k uses the 0-based index of the next candidate, not its value.) For subsets you'd record every node — nothing is ever pruned, so [3] would be a valid answer; for permutations you pick any unused element each level instead of passing start.

Pruning is what makes it tractable

The naive tree is exponential. Cut branches that can't lead to a solution: a constraint already violated (N-Queens: same column/diagonal), a duplicate (sort, then skip c == prev), or a bound exceeded. Good pruning turns "times out" into "passes."

Pitfalls

• Forgetting to un-choose → state leaks into sibling branches (the #1 bug).
• Adding the path by reference → every result points to the same (now-empty) list; add a copy.
• No pruning → exponential blow-up; prune as early as possible.

Costs, and when NOT to backtrack

• Sizes: subsets of n elements → 2ⁿ results, O(n·2ⁿ) time (copying costs the n); permutations → O(n·n!); combinations → C(n,k) leaves. Recursion stack: O(n) space.
• When NOT: if the question asks for a min/max/count over subproblems that overlap, reach for DP — backtracking enumerates configurations, DP optimizes over shared subproblems. A proven greedy choice beats both; unweighted shortest paths want BFS.

Takeaways

• choose → explore → un-choose; record a copy at complete states.
• Prune invalid/duplicate branches early — that's the difference between AC and TLE.
• Subsets (include/skip), permutations (any unused via used[]), combinations (indices ≥ start) are the same skeleton with a different "choices" rule.

---

Re-authored for this guide; backtracking-tree diagram hand-authored as SVG. See also: Recursion, the Pattern Recognition index.

I just read a lesson on **Backtracking — Choose / Explore / Un-choose, with Pruning** (DSA) and want to truly understand it. Explain Backtracking — Choose / Explore / Un-choose, with Pruning from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Backtracking — Choose / Explore / Un-choose, with Pruning** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Backtracking — Choose / Explore / Un-choose, with Pruning** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Backtracking — Choose / Explore / Un-choose, with Pruning** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.