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)
    }
}

Subsets of [1,2,3], traced

At each index, decide include/skip; the recursion tree branches, and you record every node. For permutations you instead pick an unused element each level; for "combinations" you pass a start index so you never go backwards (that's the pruned branch in the diagram).

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.

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/permutations/combinations 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.