Backtracking Patterns

Backtracking Patterns: The Art of Smart Exploration

The Treasure Hunter’s Map

Imagine you’re a treasure hunter exploring a cave with many tunnels. You walk into one tunnel. Dead end? You backtrack to the last fork and try another path. This is backtracking — exploring possibilities, and when one doesn’t work, going back to try something else.

In programming, backtracking helps us solve puzzles where we need to try many combinations until we find the right one.

1. Backtracking Fundamentals

The Core Idea

Backtracking is like playing a maze game:

1. Choose a path
2. Explore that path
3. If stuck, go back and try another path
4. Repeat until you find the exit (or try all paths)

The Magic Recipe

Every backtracking solution follows this pattern:

void backtrack(current_state) {
    // Base case: found a solution?
    if (isSolution(current_state)) {
        saveSolution(current_state);
        return;
    }

    // Try each choice
    for (choice : allChoices) {
        // Make the choice
        makeChoice(choice);

        // Explore further
        backtrack(new_state);

        // Undo the choice (BACKTRACK!)
        undoChoice(choice);
    }
}

Simple Example: Finding Exit in a Maze

void findPath(int row, int col) {
    // Found the exit?
    if (row == exitRow && col == exitCol) {
        System.out.println("Found it!");
        return;
    }

    // Mark as visited
    visited[row][col] = true;

    // Try all 4 directions
    int[] dr = {0, 0, 1, -1};
    int[] dc = {1, -1, 0, 0};

    for (int i = 0; i < 4; i++) {
        int newR = row + dr[i];
        int newC = col + dc[i];
        if (isValid(newR, newC)) {
            findPath(newR, newC);
        }
    }

    // Backtrack: unmark
    visited[row][col] = false;
}

2. Backtracking with Pruning

What is Pruning?

Imagine you’re looking for a red apple in boxes. If a box is labeled “Only Oranges,” would you open it? No! That’s pruning — skipping paths that definitely won’t lead to a solution.

Pruning makes backtracking much faster by cutting off useless branches early.

graph TD
    A["Start"] --> B{Choice 1}
    B -->|Valid| C["Explore"]
    B -->|Invalid| D["PRUNE - Skip!"]
    C --> E{Choice 2}
    E -->|Valid| F["Continue..."]
    E -->|Invalid| G["PRUNE - Skip!"]

Example: N-Queens with Pruning

Place N queens on an N×N chessboard so none attack each other.

void solveNQueens(int row) {
    if (row == n) {
        // Found valid arrangement!
        saveSolution();
        return;
    }

    for (int col = 0; col < n; col++) {
        // PRUNING: Skip if queen is under attack
        if (isSafe(row, col)) {
            placeQueen(row, col);
            solveNQueens(row + 1);
            removeQueen(row, col);
        }
        // If not safe, we SKIP (prune)
    }
}

boolean isSafe(int row, int col) {
    // Check column
    // Check diagonals
    // Return true if no queen attacks
}

3. Permutations

What are Permutations?

Given items, permutations are all possible ways to arrange them in different orders.

For [1, 2, 3], the permutations are:

• [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

That’s 3! = 6 arrangements.

The Story

You have 3 friends: Alice, Bob, and Carol. How many ways can they stand in a line for a photo?

• First position: 3 choices
• Second position: 2 remaining choices
• Third position: 1 remaining choice
• Total: 3 × 2 × 1 = 6 ways

Code Example

List<List<Integer>> result = new ArrayList<>();

void permute(int[] nums, List<Integer> current,
             boolean[] used) {
    // Base case: used all numbers
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // Skip if already used
        if (used[i]) continue;

        // Choose
        used[i] = true;
        current.add(nums[i]);

        // Explore
        permute(nums, current, used);

        // Backtrack
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

4. Combinations

What are Combinations?

Combinations are about selecting items where order doesn’t matter.

Picking 2 fruits from [Apple, Banana, Cherry]:

• {Apple, Banana}, {Apple, Cherry}, {Banana, Cherry}

That’s only 3 combinations (not 6, because {Apple, Banana} = {Banana, Apple}).

Key Difference from Permutations

Code Example

void combine(int n, int k, int start,
             List<Integer> current) {
    // Found k items
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Try numbers from start to n
    for (int i = start; i <= n; i++) {
        // Choose
        current.add(i);

        // Explore (start from i+1, not 0!)
        combine(n, k, i + 1, current);

        // Backtrack
        current.remove(current.size() - 1);
    }
}

The trick: start from i+1 to avoid duplicates and maintain order.

5. Subsets Generation

What are Subsets?

A subset is any selection of items from a set, including the empty set and the set itself.

For [1, 2], subsets are:

• [] (empty)
• [1]
• [2]
• [1, 2]

That’s 2² = 4 subsets. For n items, there are 2ⁿ subsets.

The Light Switch Analogy

Each item is like a light switch — either ON (included) or OFF (excluded).

graph TD
    A["Start []"] --> B{"Include 1?"}
    B -->|Yes| C["[1]"]
    B -->|No| D["[]"]
    C --> E{"Include 2?"}
    D --> F{"Include 2?"}
    E -->|Yes| G["[1,2]"]
    E -->|No| H["[1]"]
    F -->|Yes| I["[2]"]
    F -->|No| J["[]"]

Code Example

void subsets(int[] nums, int index,
             List<Integer> current) {
    // Every path is a valid subset
    result.add(new ArrayList<>(current));

    for (int i = index; i < nums.length; i++) {
        // Include nums[i]
        current.add(nums[i]);

        // Explore further items
        subsets(nums, i + 1, current);

        // Backtrack: exclude nums[i]
        current.remove(current.size() - 1);
    }
}

6. Combination Sum

The Problem

Given numbers and a target, find all combinations that sum to the target. Numbers can be reused!

Example: numbers = [2, 3, 5], target = 8

• [2, 2, 2, 2] = 8 ✓
• [2, 3, 3] = 8 ✓
• [3, 5] = 8 ✓

The Coin Machine Story

You have unlimited coins of certain values. Find all ways to make exact change!

Code Example

void combinationSum(int[] candidates, int target,
                    int start, List<Integer> current) {
    // Found exact target!
    if (target == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Exceeded target (pruning)
    if (target < 0) return;

    for (int i = start; i < candidates.length; i++) {
        // Choose
        current.add(candidates[i]);

        // Explore (use i, not i+1 — reuse allowed)
        combinationSum(candidates,
            target - candidates[i], i, current);

        // Backtrack
        current.remove(current.size() - 1);
    }
}

Key insight: Pass i (not i+1) to allow reusing the same number.

7. Palindrome Partitioning

What is it?

Split a string into parts where every part is a palindrome.

For "aab":

• ["a", "a", "b"] — all palindromes ✓
• ["aa", "b"] — both palindromes ✓

The Strategy

Try every possible first cut. If that piece is a palindrome, recursively partition the rest.

graph TD
    A["aab"] --> B{"First cut?"}
    B --> C["a | ab"]
    B --> D["aa | b"]
    B --> E["aab"]
    C --> F["a is palindrome ✓"]
    F --> G["Continue with 'ab'"]
    D --> H["aa is palindrome ✓"]
    H --> I["b is palindrome ✓"]
    E --> J["aab not palindrome ✗"]

Code Example

void partition(String s, int start,
               List<String> current) {
    // Partitioned entire string
    if (start == s.length()) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Try all possible endings
    for (int end = start + 1; end <= s.length(); end++) {
        String part = s.substring(start, end);

        // Only continue if palindrome (pruning!)
        if (isPalindrome(part)) {
            current.add(part);
            partition(s, end, current);
            current.remove(current.size() - 1);
        }
    }
}

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--))
            return false;
    }
    return true;
}

8. Generate Parentheses

The Problem

Generate all valid combinations of n pairs of parentheses.

For n = 3:

• ((()))
• (()())
• (())()
• ()(())
• ()()()

The Rules

1. Can add ( if we haven’t used all n opening brackets
2. Can add ) only if closing < opening (can’t close what isn’t open!)

The Balance Story

Think of it like a bank account:

• ( = Deposit $1
• ) = Withdraw $1
• Balance can never go negative!
• End with balance = 0

Code Example

void generate(int n, int open, int close,
              StringBuilder current) {
    // Used all parentheses
    if (current.length() == 2 * n) {
        result.add(current.toString());
        return;
    }

    // Can add opening bracket?
    if (open < n) {
        current.append('(');
        generate(n, open + 1, close, current);
        current.deleteCharAt(current.length() - 1);
    }

    // Can add closing bracket?
    if (close < open) {
        current.append(')');
        generate(n, open, close + 1, current);
        current.deleteCharAt(current.length() - 1);
    }
}

The Backtracking Framework Summary

All backtracking problems follow this pattern:

void backtrack(state, choices) {
    if (isGoal(state)) {
        record(state);
        return;
    }

    for (choice : choices) {
        if (isValid(choice)) {  // Pruning
            make(choice);
            backtrack(newState, newChoices);
            undo(choice);  // BACKTRACK!
        }
    }
}

When to Use Backtracking

Key Takeaways

1. Choose-Explore-Undo is the heart of backtracking
2. Pruning makes it fast by skipping dead ends early
3. Permutations care about order
4. Combinations don’t care about order
5. Subsets = all possible selections (2ⁿ)
6. Combination Sum allows reuse of elements
7. Palindrome Partitioning uses pruning for efficiency
8. Generate Parentheses uses balance rules for validity

You Did It!

You now understand backtracking — the art of smart exploration. Like a treasure hunter, you know when to push forward and when to step back. These patterns appear everywhere: from puzzle games to AI decision-making.

Keep practicing, and soon these patterns will feel as natural as walking through a maze!