Backtracking

You might have heard backtracking sounds scary because it involves “trying every possibility.” Do not worry - it is actually one of the most logical and fun techniques once you see the pattern. This guide will make it click, step by step, with simple examples.

What Is Backtracking

Backtracking is a technique where you try an option, explore it fully, and if it does not work out, you undo it and try the next option.

That is the whole idea. You make a choice, go further into the problem, and if you hit a dead end, you go back and change your choice.

Here is a simple way to picture it: imagine you are in a maze. You walk down a corridor. If it leads to a dead end, you walk back to the last fork and try a different corridor. You keep doing this until you find the exit or you have tried every path. That “walking back” step is exactly what backtracking means.

Tip

Backtracking is just recursion with an undo button. You choose something, explore what happens next, and then unchoose it before trying the next option.

Backtracking follows three simple steps at every stage:

• Choose - pick an option from the available choices
• Explore - go deeper and see what happens with that choice
• Unchoose - undo the choice so you can try the next one

Why Not Just Use Plain Recursion

Plain recursion usually solves one path through a problem. Backtracking is different because it tries all possible paths, one at a time, and throws away the ones that do not work.

Think of it like trying on outfits before a party. You put on a shirt, look in the mirror, and if it does not look right, you take it off (undo) and try a different shirt. You do not keep wearing every shirt at once - you try one, remove it, then try the next.

This “try, then undo” behavior is what separates backtracking from simple recursion. In simple recursion, you usually do not need to clean up after yourself. In backtracking, cleaning up (undoing the choice) is the whole point.

The Pattern Every Backtracking Problem Follows

Almost every backtracking solution looks like this:

function backtrack(current_choices):
    if current_choices is a complete solution:
        save or print it
        return

    for each option available right now:
        make the choice          # Choose
        backtrack(current_choices)   # Explore
        undo the choice          # Unchoose

That loop with choose, explore, unchoose inside it is the heart of backtracking. Once you spot this shape, you can solve almost any backtracking problem by filling in the blanks.

Note

This pattern is sometimes called DFS (Depth First Search) with state, because you are going as deep as possible into one choice before backing out, just like exploring a tree branch by branch.

Your First Backtracking Problem - All Subsets

A subset is any group of items you can pick from a list, including picking nothing or picking everything. For [1, 2, 3], the subsets are:

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

At every number, you have two choices: include it or skip it. That is a perfect job for backtracking.

def subsets(nums):
    result = []

    def backtrack(index, current):
        if index == len(nums):       # Reached the end - this is one full subset
            result.append(current[:])  # Save a copy of current
            return

        current.append(nums[index])   # Choose: include this number
        backtrack(index + 1, current)
        current.pop()                  # Unchoose: remove it before trying "skip"

        backtrack(index + 1, current)  # Try the path where we skip this number

    backtrack(0, [])
    return result


print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Notice the current.pop() line. That is the “unchoose” step. Without it, the list would keep growing and never go back to a clean state for the next try.

All Permutations

A permutation is every possible order of a list. For [1, 2, 3], there are 6 permutations:

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

Here the choice is “which number goes next”, and once a number is used, you cannot use it again in the same arrangement.

def permute(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):     # Path is full - found one permutation
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue               # Already used this number, skip it

            used[i] = True             # Choose
            path.append(nums[i])
            backtrack(path)            # Explore
            path.pop()                  # Unchoose
            used[i] = False

    backtrack([])
    return result


print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Tracing it for [1, 2]:

backtrack([])
├── choose 1 -> path = [1]
│     └── choose 2 -> path = [1, 2]  -> FULL! save [1, 2]
│         unchoose 2 -> path = [1]
│   unchoose 1 -> path = []
├── choose 2 -> path = [2]
│     └── choose 1 -> path = [2, 1]  -> FULL! save [2, 1]
│         unchoose 1 -> path = [2]
│   unchoose 2 -> path = []

See how the path grows, hits a full solution, then shrinks back down before trying the next branch? That shrinking is backtracking in action.

Combination Sum - Picking Numbers That Add Up to a Target

Given a list of numbers and a target, find all the ways to pick numbers (you can reuse numbers) that add up exactly to the target.

Example: numbers = [2, 3, 6, 7], target = 7

Possible answers: [7] and [2, 2, 3]

def combination_sum(candidates, target):
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:                # Hit the target exactly
            result.append(current[:])
            return
        if remaining < 0:                  # Went over the target, this path is dead
            return

        for i in range(start, len(candidates)):
            current.append(candidates[i])              # Choose
            backtrack(i, current, remaining - candidates[i])  # Explore (i, not i+1, since we can reuse)
            current.pop()                                # Unchoose

    backtrack(0, [], target)
    return result


print(combination_sum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]

Notice the if remaining < 0: return line. This is called pruning - cutting off a path early because you already know it cannot lead to a valid answer. Pruning is what makes backtracking fast instead of just trying everything blindly.

Tip

Pruning is one of the most important ideas in backtracking. If you can tell a path is doomed before fully exploring it, stop right there instead of wasting time going deeper.

N-Queens - The Most Famous Backtracking Problem

The N-Queens problem asks: can you place N queens on an N x N chessboard so that no two queens attack each other? Queens attack in the same row, same column, or along diagonals.

For a 4x4 board, here is one valid answer:

. Q . .
. . . Q
Q . . .
. . Q .

The idea: place queens one row at a time. For each row, try every column. If placing a queen there is safe (no other queen can attack it), place it and move to the next row. If no column works, go back and move the queen in the previous row.

def solve_n_queens(n):
    result = []
    board = [-1] * n   # board[row] = column where the queen is placed

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            if prev_col == col:                       # same column
                return False
            if abs(prev_col - col) == abs(prev_row - row):  # same diagonal
                return False
        return True

    def backtrack(row):
        if row == n:                  # Placed a queen in every row successfully
            result.append(board[:])
            return

        for col in range(n):
            if is_safe(row, col):
                board[row] = col       # Choose
                backtrack(row + 1)     # Explore
                board[row] = -1        # Unchoose

    backtrack(0)
    return result


solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")   # Found 2 solutions
print(solutions[0])                            # [1, 3, 0, 2]

Each number in the answer tells you which column the queen sits in for that row. So [1, 3, 0, 2] means: row 0 has a queen in column 1, row 1 has a queen in column 3, and so on.

This problem shows off backtracking perfectly: you try a placement, check if it is safe, and the moment it is not, you back out and try the next column - no need to check every single arrangement on the whole board.

Sudoku Solver

Sudoku is a great real-world example of backtracking. You fill empty cells with numbers 1-9 so that no number repeats in any row, column, or 3x3 box.

The approach: find an empty cell, try numbers 1 through 9, and for each number check if it breaks any rule. If it is valid, place it and move to the next empty cell. If you get stuck later, come back and try a different number.

def solve_sudoku(board):
    def is_valid(row, col, num):
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False

        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for r in range(box_row, box_row + 3):
            for c in range(box_col, box_col + 3):
                if board[r][c] == num:
                    return False
        return True

    def backtrack():
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:    # Found an empty cell
                    for num in range(1, 10):
                        if is_valid(row, col, num):
                            board[row][col] = num     # Choose
                            if backtrack():             # Explore
                                return True
                            board[row][col] = 0         # Unchoose

                    return False    # No number worked here, trigger backtrack

        return True   # No empty cells left, the board is solved

    backtrack()
    return board

This looks long, but it is the exact same choose, explore, unchoose pattern you have already seen, just with a more detailed “is this safe” check.

Word Search - Finding a Word in a Grid

Given a grid of letters, check if a word can be formed by moving up, down, left, or right between adjacent letters, without reusing the same cell twice.

Grid:
A B C E
S F C S
A D E E

Word: "ABCCED" -> found by following a path through the grid

def word_search(grid, word):
    rows, cols = len(grid), len(grid[0])

    def backtrack(row, col, index):
        if index == len(word):                # Matched the whole word
            return True
        if row < 0 or row >= rows or col < 0 or col >= cols:
            return False
        if grid[row][col] != word[index]:
            return False

        temp = grid[row][col]
        grid[row][col] = "#"     # Mark as visited (choose)

        found = (
            backtrack(row + 1, col, index + 1) or
            backtrack(row - 1, col, index + 1) or
            backtrack(row, col + 1, index + 1) or
            backtrack(row, col - 1, index + 1)
        )

        grid[row][col] = temp     # Unmark (unchoose) so other paths can reuse this cell

        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

The marking and unmarking of grid[row][col] is the “choose” and “unchoose” step here. You temporarily block a cell so you do not walk over it twice in the same path, then free it up again so a different starting path can use it.

How to Approach Any Backtracking Problem

Backtracking problems all look different on the surface, but the thinking process is always the same:

1. Figure out what a “choice” looks like - is it picking a number, placing a queen, choosing a letter? Define it clearly.

2. Figure out what a “complete solution” looks like - when do you stop and save the answer? This is your base case.

3. Write the choose, explore, unchoose loop - try each option, recurse, then undo before trying the next option.

4. Add a safety check (pruning) - can you tell early that a path is invalid? Stop there instead of going deeper.

5. Test it on a tiny example - 2 or 3 items, not the full-size problem, so you can trace it by hand.

Tip

If you ever get confused while writing backtracking code, just ask yourself: “What do I need to undo before trying the next option?” That single question solves most bugs in backtracking code.

Common Backtracking Patterns

Pattern	What it looks like	Example problems
Include or skip	At each item, choose to take it or leave it	Subsets, Subset Sum
Pick in order, no repeats	Use each item exactly once, order matters	Permutations
Pick with reuse allowed	Same item can be picked more than once	Combination Sum
Place and check safety	Place something, verify it does not break a rule	N-Queens, Sudoku
Path on a grid	Move step by step, mark visited, then unmark	Word Search, Maze problems

Backtracking vs Plain Recursion vs DP

It helps to know when backtracking is the right tool compared to its cousins:

Situation	Use this
Need to try every possible combination or arrangement	Backtracking
One clear path down to a smaller version of the same problem	Plain Recursion
Same subproblems repeat again and again, need the best answer	Dynamic Programming
Need to undo a choice before trying a different one	Backtracking

Caution

A common mistake: forgetting to undo a choice. If you skip the “unchoose” step, your function will think previous choices are still active, and your results will come out wrong or incomplete. Always pair every “choose” with an “unchoose”.

Why Backtracking Can Be Slow (And How Pruning Helps)

Backtracking explores a tree of choices, and that tree can get huge. For permutations of n items, there are n! possible orders. For subsets, there are 2ⁿ possible groups. This means backtracking can be slow for large inputs.

This is exactly why pruning matters so much. Every time you stop early because a path is clearly invalid, you cut off an entire branch of that tree, including everything that would have come after it.

Without pruning:           With pruning:
        *                        *
      / | \                    / | \
     *  *  *                  *  X  *      <- X branch cut off early,
    /|  |  |\                /|     |\        saving all the work
   * * * * * *              * *     * *       underneath it

The lesson: always look for a way to detect a bad path as early as possible. It is the difference between a backtracking solution that runs instantly and one that takes forever.

Quick Reference

Choose, Explore, Unchoose

The heart of every backtracking solution. Make a choice, recurse to explore it, then undo the choice before trying the next option.

Subsets

At each item, branch into two paths: include it or skip it. Results in 2ⁿ possible subsets.

Permutations

Try every unused item at each position. Mark items as used, then unmark them when backtracking.

Combination Sum

Pick numbers that add up to a target. Allow reuse by not moving the start index forward. Prune when the running total goes over target.

N-Queens / Sudoku

Place something, check if it is safe, explore further if it is. Undo the placement if no safe option works further down.

Pruning

Stop exploring a path as soon as you know it cannot lead to a valid answer. This is what keeps backtracking fast.

Summary

The Core Idea

• Backtracking means choose, explore, and undo if it does not work out
• It tries every possible option but throws away the ones that fail early
• Every backtracking function needs a clear “complete solution” check and a way to undo a choice
• Pruning (stopping early on bad paths) is what makes backtracking practical instead of painfully slow

Problems Covered

• Subsets - include or skip each item, 2ⁿ total combinations
• Permutations - try every unused item at each position, n! total orders
• Combination Sum - pick numbers that add up to a target, reuse allowed
• N-Queens - place queens row by row, check safety before placing
• Sudoku Solver - fill empty cells while respecting row, column, and box rules
• Word Search - walk through a grid marking visited cells, then unmarking them

Interview Tips

• Spot the choose, explore, unchoose loop - it is the same shape in almost every problem
• Always undo a choice right after exploring it, no exceptions
• Add pruning wherever you can detect a path is already invalid
• Draw the choice tree by hand for small inputs before coding
• If the problem says “all possible ways”, “all combinations”, or “all arrangements” - think backtracking
• Backtracking and DP often solve similar-sounding problems - DP is for optimal counts/values, backtracking is for listing out every actual answer