Backtracking

Backtracking is a systematic way to explore all possible solutions by building them incrementally and abandoning paths that cannot lead to valid solutions.

Think of it like exploring a maze:

• •You walk down a path until you hit a dead end
• •Then you "backtrack" to the last decision point
• •Try a different path
• •Repeat until you find the exit (or explore all paths)

Why is backtracking important?

About 15-20% of coding interview questions involve backtracking. It's essential for:

• •Generating all combinations/permutations
• •Solving puzzles (Sudoku, N-Queens)
• •Finding paths in graphs/grids
• •String partitioning problems

The Core Idea:

Time Complexity:

• •Subsets: O(2^n) - each element can be included or not
• •Permutations: O(n!) - n choices for first, n-1 for second, etc.
• •Generally exponential - but pruning helps!

Almost every backtracking problem follows this template:

The 3 Key Questions:

1. •

   What is the goal? (Base case)

   • Subsets: any state is valid
   • Permutations: path.length === n
   • Combination Sum: remaining === 0
2. •

   What are the choices?

   • Subsets: elements from index start to end
   • Permutations: all unused elements
   • Grid: 4 directions (up, down, left, right)
3. •

   When to prune?

   • Skip duplicates
   • Skip invalid states early
   • Check constraints before recursing

Generate all possible subsets (the power set) of a given array.

Problem: Given [1, 2, 3], return all subsets.

Visualization:

Key Insight:

• •At each position, we have a choice: include element or not
• •Use start index to avoid duplicates ([1,2] and [2,1] are same subset)
• •Add current path to result at EVERY step (not just leaves)

Decision Tree:

Watch how backtracking builds all 2^n subsets by making include/exclude decisions at each element.

Generate all possible orderings of elements.

Problem: Given [1, 2, 3], return all permutations.

Key Difference from Subsets:

• •Subsets: [1,2] and [2,1] are the SAME (order doesn't matter)
• •Permutations: [1,2] and [2,1] are DIFFERENT (order matters)

Visualization:

Key Insight:

• •Use a used array to track which elements are already in path
• •Start from index 0 every time (not from start)
• •Only add to result when path has all elements

Why used[] instead of start?

Visualize how the used[] array tracks which elements are available as we build all n! orderings.

Choose exactly k elements from n elements.

Problem: Given n=4, k=2, return all combinations of 2 numbers from [1,2,3,4].

Visualization:

Pruning Optimization: If we need k elements and have path.length already, we need k - path.length more. So we only iterate while i <= n - (k - path.length) + 1.

When input has duplicates, we need extra logic to avoid duplicate results.

Problem: [1, 2, 2] subsets should give [], [1], [2], [1,2], [2,2], [1,2,2] NOT: [], [1], [2], [2], [1,2], [1,2], [2,2], [1,2,2]

The Solution: Sort + Skip

Visualization:

For Permutations with Duplicates: Slightly different - skip if nums[i] === nums[i-1] && !used[i-1] This ensures we use duplicates in order.

Find combinations that sum to a target.

Variations:

Combination Sum (can reuse elements):

Key Insight for Reuse:

• •backtrack(i, ...) allows reusing same element
• •backtrack(i + 1, ...) moves to next element

Search for patterns in a 2D grid by exploring all paths.

Problem: Find if a word exists in a grid by moving up/down/left/right.

Visualization:

Grid Backtracking Pattern:

1. •Try starting from each cell
2. •At each cell, try 4 directions
3. •Mark cell as visited before exploring
4. •Unmark after exploring (backtrack)

Key Insights:

• •Use the grid itself to mark visited (save space)
• •Replace char with '#', restore after backtracking
• •Check bounds and character match FIRST (pruning)

Common Grid Problems:

• •Word Search
• •N-Queens
• •Sudoku Solver
• •Rat in a Maze
• •Knight's Tour

Place N queens on an N×N board so no two attack each other.

Constraints:

• •No two queens in same row
• •No two queens in same column
• •No two queens on same diagonal

Visualization (N=4):

Smart Approach:

• •Place one queen per row (guarantees no row conflicts)
• •Track used columns with a Set
• •Track diagonals:
  • Main diagonal: row - col is constant
  • Anti-diagonal: row + col is constant

Diagonal Insight:

Watch the backtracking algorithm place queens on a chessboard, detecting conflicts and trying alternatives.

Generate all valid combinations of n pairs of parentheses.

Constraints:

• •At any point, open count >= close count
• •Total open = Total close = n

Visualization (n=2):

Key Insight: We can add '(' if open < n, and ')' if close < open.

This is different from other backtracking because we don't iterate through choices - we make two specific decisions at each step.

Partition a string such that every substring is a palindrome.

Problem: "aab" -> [["a","a","b"], ["aa","b"]]

Visualization:

Key Insight: At each position, try all possible first partitions. Only continue if current partition is a palindrome.

Edge Cases to Handle:

1. Empty Input

2. Single Element

3. All Duplicates

4. Large Input (Pruning Critical)

5. No Solution Exists

Common Mistakes:

Quick reference for choosing the right backtracking approach:

By Problem Type:

Key Differences:

Handling Duplicates:

• •Always sort first
• •Skip: i > start && nums[i] == nums[i-1]
• •For permutations: also check !used[i-1]

Pruning Strategies:

• •Check constraints before recursing
• •For sums: skip if remaining < 0
• •For combinations: check if enough elements remain
• •For grids: check bounds and visited first

Subsets Template:

Permutations Template:

Combination Sum Template:

Grid Backtracking Template:

Interview Tips:

• •Draw the decision tree for small input
• •Identify: What's the goal? What are choices? When to prune?
• •Always copy path when adding to result
• •Remember to undo ALL state changes when backtracking