---
title: "Backtracking algorithm: the three-line template, Python code and N Queens"
url: https://algopath.pro/blog/backtracking-algorithm
language: en
summary: "Search with undo for all permutations, all subsets and N queens. The template, Python code, a traced run, how it differs from DP and the mistakes that break it."
updated: 2026-10-18
---

# Backtracking algorithm: the three-line template, Python code and N Queens

**Short answer.** A backtracking algorithm builds a solution one choice at a time. A choice leads to a dead end: undo it, try the next one. It solves "all permutations", "all subsets", "N queens" and sudoku. Below: the template, Python code, a traced run and the usual mistakes.

 

## What is a backtracking algorithm?

 

You hold a partial solution. At each step you pick the next element from the valid options. If the pick leads to a full solution, record it. If it leads nowhere, undo it and pick the next.

 

It is depth-first search over a tree of choices. A node is a partial solution. An edge is one choice. Leaves are full solutions or dead ends.

 

The word backtrack names the main move. Take a step, come back, take a different one. After the return, the state is exactly what it was before the step.

 

The difference from brute force is early pruning. Two queens already attack each other: the other six are never placed.

 

## When does a problem need a backtracking algorithm?

 

- "All permutations", "all subsets", "all combinations".
- "All ways to split a string", "all paths through a maze".
- "Place N queens", "solve the sudoku".
- "Find any valid arrangement" with n under 20.

 

The shared signal: every answer, or one answer under hard constraints. And n is small. If the task only counts answers, dynamic programming usually fits better.

 

## How does the backtracking template work?

 

- A function receives the current partial solution, path.
- If path is complete, record a copy and return.
- For each valid option: append it to path, recurse, then pop it.

 

The three lines "append, recurse, pop" are the backtrack. Without the pop, path grows forever.

 

## What does one run look like?

 

Permutations of [1, 2, 3]. Path is empty. Take 1: [1]. Take 2: [1, 2]. Take 3: [1, 2, 3], complete, recorded. Pop 3, no options left. Pop 2.

 

Take 3: [1, 3]. Take 2: [1, 3, 2], recorded. Back to empty. Take 2 first: [2, 1, 3], [2, 3, 1]. Then [3, 1, 2], [3, 2, 1]. Six answers, none missed.

 

## How do you write a backtracking algorithm in Python?

 

```
def permutations(nums):
    result, path, used = [], [], [False] * len(nums)

    def go():
        if len(path) == len(nums):
            result.append(path[:])          # a copy, not a reference
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            go()
            path.pop()                      # backtrack
            used[i] = False

    go()
    return result

def subsets(nums):
    result, path = [], []

    def go(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            go(i + 1)
            path.pop()

    go(0)
    return result
```

 

The start parameter in subsets forbids going back. That is why [1, 2] and [2, 1] are not counted twice.

 

## How does backtracking compare with its neighbours?

 

| Pattern | Gives you | Size of n | Example |
| --- | --- | --- | --- |
| Backtracking | All solutions, or one under constraints | Up to 15-20 | N queens, permutations |
| Dynamic programming | A count or an optimum | Thousands | Number of paths, knapsack |
| Depth-first search | Reachability, components | Millions | Islands in a grid |
| Greedy | An optimum without search | Any | Interval scheduling |

 

## How does backtracking solve N Queens?

 

Place one queen per row. For row r, try every column c. Skip it if the column or a diagonal is taken.

 

Keep three sets: used columns, diagonals r - c, and diagonals r + c. The check costs O(1). Reaching row n means a full board, record it.

 

For n = 8, brute force has 8 to the power 8 boards. Pruning leaves a few thousand.

 

## What mistakes break a backtracking algorithm?

 

- Recording path instead of path[:]. Every answer becomes the same empty list.
- Forgetting the pop after the recursive call.
- Checking constraints only at the end instead of every step. Pruning never happens.
- Not sorting the input when it has duplicates, so equal answers repeat.

 

## How do you explain backtracking in an interview?

 

Say: I need every solution and n is small. I build the answer step by step and undo. Name the three template lines. Say where you prune.

 

State the complexity honestly: O(n!) for permutations, O(2ⁿ) for subsets. Then say pruning cuts the real step count a lot.

 

Drill this pattern on the [backtracking](/patterns/backtracking) page. The base skill lives on the [recursion](/patterns/recursion) page.

 

## FAQ

 

### How is backtracking different from depth-first search?

 

The mechanics match. Backtracking builds a solution and undoes a step. DFS just marks nodes as visited.

 

### How do you remove duplicates in subsets with repeated values?

 

Sort the input. In the loop, skip an element equal to the previous one. Do that only when the previous one was skipped at this level.

 

### Where does backtracking show up in real systems?

 

Constraint solvers: timetables, assigning jobs to machines. Parsers that try one grammar rule, fail, and try another. Game engines that search moves a few steps ahead.

 

### When is backtracking too slow?

 

When n is above 20 and pruning is weak. Then look for dynamic programming or a greedy rule.