Skip to main content

DSAPath20 minintermediate

Backtracking

Backtracking explores a decision tree by choosing, recursing, and undoing choices. It is DFS for search spaces where invalid partial states can be pruned.

DifficultyIntermediate
TierTier 2
ModuleSearch Foundations
LanguagesPython

Why This Matters

Backtracking is the workhorse for subsets, permutations, combinations, constraint satisfaction, word search, N-Queens, Sudoku, and many "generate all valid answers" problems.

The invariant is the partial solution: it must remain internally consistent before recursion continues.

Prerequisite Check

Review DFS and Recursion. Backtracking is DFS over a decision tree with explicit choice and undo steps.

Learning Objectives

By the end, you should be able to:

  • Identify the decision tree for a problem.
  • Write choose/recurse/undo code without leaking state.
  • Use pruning to stop impossible branches early.
  • Explain output-size lower bounds.
  • Distinguish backtracking from dynamic programming.

Core Idea

Maintain a partial answer. At each step, try a legal choice, recurse, then undo the choice before trying the next option.

PatternInvariantTypical problem
Subsetspath contains choices from processed prefixpower set
Permutationspath contains no repeated used itemarrangements
Combinationsindices increase to avoid duplicateschoose k
Constraint searchpartial state violates no constraintN-Queens, Sudoku

Visual Model

subsets of [1, 2]

             []
          /      \
       [1]        []
      /   \      /  \
  [1,2]  [1]   [2]  []

Each root-to-leaf path is one answer or one rejected candidate.

Non-Example or Failure Mode

Backtracking is not automatically efficient. If there is no pruning and the output is exponential, the runtime is exponential. That is not a bug; it is often unavoidable because there are exponentially many answers.

Worked Example

Generate subsets of [1, 2, 3].

At index 0, choose or skip 1.
At index 1, choose or skip 2.
At index 2, choose or skip 3.
At index 3, record the current path.

The invariant is that path contains exactly the chosen values from earlier indices.

LeetCode-Style Problem Patterns

PatternRecognition signalMove
Generate all subsets"all possible subsets"binary choose/skip recursion
Permutations"all arrangements"used set plus path
Combination sum"sum to target"prune when remaining target is negative
Word search"path in grid without reusing cells"mark cell, recurse, unmark

Common Mistakes

MistakeCorrection
Forgetting to undo state.Pop or unmark after the recursive call.
Appending the same mutable list object.Append a copy such as path[:].
Missing duplicate handling.Sort and skip equal choices at the same depth when needed.
Calling it polynomial because the code has one loop.Count the size of the decision tree and output.

Diagnostic Questions

Question typeQuestionAnswer signal
DefinitionWhat does backtracking undo?The local choice added before the recursive call.
Example / non-exampleIs binary search backtracking?No; it discards half the search space without exploring alternatives.
ComputationWhy are subsets O(2^n)?There are 2^n subsets to output.
ProofWhat invariant keeps subset generation correct?At depth i, the path reflects choices for the first i items.
TransferWhen does DP replace backtracking?When many branches recompute the same subproblem state.

Exercises

Beginner:

  • Draw the subset decision tree for three items.
  • Explain why path[:] is needed when recording answers.
  • Generate all binary strings of length n.

Intermediate:

  • Implement permutations with a used set.
  • Add pruning to combination sum.

Challenge:

  • Implement N-Queens and explain which constraint checks prune the search tree.

Diagram Recommendation

Type: decision-tree trace.

Caption: "Backtracking is DFS where each edge is a choice and each return undoes that choice."

Purpose: Make choose/recurse/undo visible and prevent mutable-state leaks.

Implementation Task

Implement subsets and permutations. Test that the algorithm returns independent list objects, not repeated references to the same path.

Run backtracking subsets

This cell generates subsets and permutations with explicit choose/recurse/undo structure.

Output will appear here.

Next Topics

References