Backtracking

Step 1 Understand it

Remember it by

Choose, explore, un-choose — and stop early when a path can't work.

Watch it happen

The idea

Build a solution one choice at a time. After each choice, explore everything that follows, then undo the choice and try the next one. It walks a tree of decisions; pruning cuts off branches that can't succeed.

Picture it

flowchart TD
  R["[ ]"] -->|"take 1"| A["[1]"]
  R -->|"skip 1"| B["[ ]"]
  A -->|"take 2"| C["[1, 2]"]
  A -->|"skip 2"| D["[1]"]
  B -->|"take 2"| E["[2]"]
  B -->|"skip 2"| F["[ ]"]

Analogy

Walking a maze with chalk. At every fork, pick a path; at a dead end, walk back to the last fork, rub out your mark and try the next path.

Where the analogy breaks

In a maze you stop at the exit. Here you usually want every solution, so you record each one and keep exploring.

Step 2 Recognise it

Words that signal it

• 'All' combinations, permutations, subsets or partitions
• 'Generate every valid …' (parentheses, palindrome splits)
• Small input (n ≤ 15–20): exponential time is expected
• Placing things under rules: N-Queens, Sudoku, word search on a grid

Don't confuse it with

• Dynamic Programming: 'How many ways' or 'the best way' with repeated subproblems → DP. 'List them all' → backtracking.
• BFS: Shortest number of steps → BFS. Every possible arrangement → backtracking.

Gut check

Do they want every possible arrangement, and n is small? → backtracking.

How to recognise it in an interview

The problem wants 'all possible combinations', 'subsets', 'permutations', or specifically mentions finding paths on a board.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def backtrack_all(nums):
    results, path = [], []

    def backtrack(start):
        results.append(path[:])          # record a COPY (or only when complete)
        for i in range(start, len(nums)):
            # (optional) prune: skip choices that can't work
            path.append(nums[i])          # choose
            backtrack(i + 1)              # explore (use i to allow reuse)
            path.pop()                    # un-choose

    backtrack(0)
    return results

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
        // Deep copy the current list and add it to our final results
        result.add(new ArrayList<>(current));
        
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                  // Make a choice
            backtrack(result, current, nums, i + 1); // Explore further
            current.remove(current.size() - 1);    // Undo the choice (Backtrack!)
        }
    }
}

Common mistakes

• Appending path instead of path[:] (a copy): every saved answer then changes as path changes.
• Forgetting to undo the choice (path.pop()) after exploring.
• Getting duplicates: sort first and skip equal neighbours at the same depth (Subsets II, Combination Sum II).

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def subsets(nums):
    results, path = [], []
    def backtrack(start):
        results.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return results

def combination_sum(candidates, target):
    results, path = [], []
    def backtrack(start, total):
        if total == target:
            results.append(path[:])
            return
        if total > target:
            return                         # prune
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, total + candidates[i])   # i: reuse allowed
            path.pop()
    backtrack(0, 0)
    return results

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Medium

1. Mark "Subsets" as solved Subsets Medium

   Return every subset of a list of distinct numbers.

   Show answer

   Technique: Backtracking (take or skip)

   The clue: 'All subsets'.

   The trick: Record the path at every call; for each later number, choose it, recurse, un-choose it.

2. Mark "Combination Sum" as solved Combination Sum Medium

   Find all combinations (numbers can be reused) that add up to a target.

   Show answer

   Technique: Backtracking with reuse

   The clue: 'All combinations' that hit a target, reuse allowed.

   The trick: Recurse with the same index to reuse a number; stop when the total passes the target.

3. Mark "Combination Sum II" as solved Combination Sum II Medium

   Find all unique combinations that add up to a target; each number used at most once, and the input has duplicates.

   Show answer

   Technique: Backtracking + sort + skip duplicates

   The clue: 'All unique combinations' with repeated input values.

   The trick: Sort; at the same depth, skip a number equal to the previous one; recurse with i + 1.

4. Mark "Permutations" as solved Permutations Medium

   Return every ordering of a list of distinct numbers.

   Show answer

   Technique: Backtracking with a used set

   The clue: 'All permutations' = every order.

   The trick: At each position try every unused number; mark it used, recurse, unmark.

5. Mark "Subsets II" as solved Subsets II Medium

   Return every subset when the input has duplicates, with no duplicate subsets.

   Show answer

   Technique: Backtracking + sort + skip duplicates

   The clue: 'All subsets' but the input repeats values.

   The trick: Sort; skip nums[i] when it equals nums[i − 1] at the same depth (i > start).

6. Mark "Generate Parentheses" as solved Generate Parentheses Medium

   Generate every valid string of n pairs of brackets.

   Show answer

   Technique: Backtracking with counts

   The clue: 'Generate all valid' strings.

   The trick: Add '(' while open < n; add ')' while close < open.

7. Mark "Word Search" as solved Word Search Medium

   Decide whether a word can be traced in a letter grid by moving up, down, left or right without reusing a cell.

   Show answer

   Technique: Grid backtracking (DFS)

   The clue: Trace a path on a grid where a cell can't be reused.

   The trick: DFS from every cell, mark the cell used during the path and unmark it when returning.

8. Mark "Palindrome Partitioning" as solved Palindrome Partitioning Medium

   Split a string into pieces so that every piece is a palindrome; return all such splits.

   Show answer

   Technique: Backtracking on cut positions

   The clue: 'All ways to split'.

   The trick: Try every end position for the next piece; only recurse when that piece is a palindrome.

9. Mark "Letter Combinations of a Phone Number" as solved Letter Combinations of a Phone Number Medium

   Return every letter string a phone keypad number could stand for.

   Show answer

   Technique: Backtracking over digits

   The clue: 'All combinations', one choice per digit.

   The trick: For each digit, try each of its letters and recurse to the next digit.

Hard

1. Mark "N Queens" as solved N Queens Hard

   Place n queens on an n × n board so that none attack each other; return all boards.

   Show answer

   Technique: Backtracking row by row with sets

   The clue: Placing items under rules, all solutions.

   The trick: Place one queen per row; track used columns and both diagonals (r − c and r + c) in sets.

What to say in the interview

'Because we need all combinations, the time complexity will naturally be exponential. I will use backtracking to explore the state-space tree.'

Follow-up prep

How do you avoid duplicate subsets if the input array has duplicate numbers?