Backtracking explores a space of candidate solutions by building them step by step and abandoning a partial solution the moment it can no longer lead to a valid answer — pruning whole branches of the recursion tree instead of generating every combination.

Recursion tree for permutations of ABC without the substring "AB" — two branches are cut before they are expanded

               ( )                         choose a value for position 0
      ┌─────────┼─────────┐
     (A)       (B)       (C)
  ┌───┴───┐  ┌──┴──┐   ┌──┴──┐
(AB)   (AC) (BA) (BC) (CA) (CB)         choose a value for position 1
  ✘      │    │    │    ✘    │           ✘ = "AB" appeared → prune this branch
       (ACB)(BAC)(BCA)     (CBA)         every surviving leaf is a solution

The template: choose, explore, un-choose

Every backtracking solution is the same recursive function. Only the three parts in the comments change from problem to problem.

The backtracking template — undo must perfectly reverse apply

solve(state):
    if state is a complete solution:       # base case
        record / print it
        return

    for each option in candidates(state):  # the branching
        if not feasible(option, state):    # ← pruning: skip dead branches early
            continue
        apply(option, state)               # choose
        solve(state)                       # explore
        undo(option, state)                # un-choose (restore the state exactly)

Choose
Place a queen, step onto a cell, write a digit — mutate the shared state.
Explore
Recurse to fill the next position. If it returns success and you only want one solution, return immediately.
Un-choose
Undo the mutation so the loop can try the next option on a clean state. Forgetting this step is the #1 bug.

Technique	Explores	Prunes?	Reuses sub-results?	Typical problems
Plain recursion / brute force	every candidate	no	no	generate all subsets or permutations
Backtracking	candidates in a DFS order	yes — as soon as a partial solution is infeasible	no	N-Queens, Sudoku, maze paths, constraint satisfaction
Dynamic programming	overlapping sub-problems	no	yes — memoised	optimisation with optimal substructure
Branch and bound	candidates in a best-first order	yes — by a cost bound	no	optimisation (TSP, 0/1 knapsack exact)

Permutations without "AB" as a substring

Given a string, print all permutations that do not contain "AB" as a substring. The brute-force version generates all n! permutations and filters them at the leaves; backtracking checks the constraint while the permutation is being built and never expands a prefix that already contains "AB".

Python

def permute(chars, l, found):
    n = len(chars)
    if l == n:                                           # every position fixed — a complete permutation
        found.append("".join(chars))
        return
    for i in range(l, n):
        chars[l], chars[i] = chars[i], chars[l]          # choose: put chars[i] at position l
        if not (l > 0 and chars[l - 1] == 'A' and chars[l] == 'B'):   # prune: "AB" just appeared
            permute(chars, l + 1, found)                 # explore
        chars[l], chars[i] = chars[i], chars[l]          # un-choose

found = []
permute(list("ABC"), 0, found)
print(" ".join(found))
print("count:", len(found))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void permute(string& s, int l, vector<string>& found) {
    int n = s.size();
    if (l == n) { found.push_back(s); return; }          // every position fixed — a complete permutation
    for (int i = l; i < n; i++) {
        swap(s[l], s[i]);                                  // choose: put s[i] at position l
        if (!(l > 0 && s[l - 1] == 'A' && s[l] == 'B'))    // prune: "AB" just appeared
            permute(s, l + 1, found);                      // explore
        swap(s[l], s[i]);                                  // un-choose
    }
}

int main() {
    string s = "ABC";
    vector<string> found;
    permute(s, 0, found);
    for (size_t i = 0; i < found.size(); i++) cout << (i ? " " : "") << found[i];
    cout << "\ncount: " << found.size() << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void permute(char[] s, int l, List<String> found) {
        if (l == s.length) { found.add(new String(s)); return; }   // every position fixed
        for (int i = l; i < s.length; i++) {
            char t = s[l]; s[l] = s[i]; s[i] = t;                 // choose: put s[i] at position l
            if (!(l > 0 && s[l - 1] == 'A' && s[l] == 'B'))        // prune: "AB" just appeared
                permute(s, l + 1, found);                          // explore
            t = s[l]; s[l] = s[i]; s[i] = t;                      // un-choose
        }
    }

    public static void main(String[] args) {
        List<String> found = new ArrayList<>();
        permute("ABC".toCharArray(), 0, found);
        System.out.println(String.join(" ", found));
        System.out.println("count: " + found.size());
    }
}

JavaScript

function permute(chars, l, found) {
    if (l === chars.length) { found.push(chars.join("")); return; }   // every position fixed
    for (let i = l; i < chars.length; i++) {
        [chars[l], chars[i]] = [chars[i], chars[l]];                  // choose: put chars[i] at position l
        if (!(l > 0 && chars[l - 1] === 'A' && chars[l] === 'B'))     // prune: "AB" just appeared
            permute(chars, l + 1, found);                             // explore
        [chars[l], chars[i]] = [chars[i], chars[l]];                  // un-choose
    }
}

const found = [];
permute([..."ABC"], 0, found);
console.log(found.join(" "));
console.log("count:", found.length);

Output

ACB BAC BCA CBA
count: 4

Time O(n · n!) worst case — far fewer nodes are visited thanks to pruning · Space O(n) recursion depth

Rat in a maze

A rat starts in the top-left cell (0, 0) of an N × N maze and must reach the bottom-right cell (N-1, N-1). A 1 is an open cell, a 0 is a wall. Only two moves are allowed: down and right. Print the path as a matrix of 1s, or report that no path exists.

The rat may only move down or right; dead ends are un-marked when the recursion backs out

maze              path found
1 0 0 0           1 0 0 0        (0,0) ↓ (1,0) → (1,1) ↓ (2,1) ↓ (3,1) → (3,2) → (3,3)
1 1 0 1           1 1 0 0
0 1 0 0           0 1 0 0        the 1 at (1,3) is open but unreachable with down/right moves
0 1 1 1           0 1 1 1

Reject
Outside the grid, or the cell is a wall → return false.
Mark
path[r][c] = 1. If this is the destination → return true.
Try down, then right
If either recursive call succeeds, keep the mark and return true.
Backtrack
Neither move led anywhere: path[r][c] = 0, return false.

Python

def solve_maze(maze):
    n = len(maze)
    path = [[0] * n for _ in range(n)]

    def solve(r, c):
        if r >= n or c >= n or maze[r][c] == 0:      # off the grid or a wall
            return False
        path[r][c] = 1                               # choose: step on this cell
        if r == n - 1 and c == n - 1:                # reached the destination
            return True
        if solve(r + 1, c) or solve(r, c + 1):       # explore: down first, then right
            return True
        path[r][c] = 0                               # un-choose: dead end
        return False

    return path if solve(0, 0) else None

maze = [[1, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 1, 0, 0],
        [0, 1, 1, 1]]
path = solve_maze(maze)
if path is None:
    print("No path exists")
else:
    print("path:")
    for row in path:
        print(" ".join(map(str, row)))

C++

#include <iostream>
#include <vector>
using namespace std;

bool solve(const vector<vector<int>>& maze, int r, int c, vector<vector<int>>& path) {
    int n = maze.size();
    if (r >= n || c >= n || maze[r][c] == 0) return false;   // off the grid or a wall
    path[r][c] = 1;                                           // choose: step on this cell
    if (r == n - 1 && c == n - 1) return true;                // reached the destination
    if (solve(maze, r + 1, c, path) || solve(maze, r, c + 1, path)) return true;   // explore: down, then right
    path[r][c] = 0;                                           // un-choose: dead end
    return false;
}

int main() {
    vector<vector<int>> maze = {{1, 0, 0, 0},
                                {1, 1, 0, 1},
                                {0, 1, 0, 0},
                                {0, 1, 1, 1}};
    int n = maze.size();
    vector<vector<int>> path(n, vector<int>(n, 0));
    if (!solve(maze, 0, 0, path)) { cout << "No path exists\n"; return 0; }
    cout << "path:\n";
    for (auto& row : path) {
        for (int j = 0; j < n; j++) cout << (j ? " " : "") << row[j];
        cout << "\n";
    }
}

Java

public class Main {
    static boolean solve(int[][] maze, int r, int c, int[][] path) {
        int n = maze.length;
        if (r >= n || c >= n || maze[r][c] == 0) return false;   // off the grid or a wall
        path[r][c] = 1;                                           // choose: step on this cell
        if (r == n - 1 && c == n - 1) return true;                // reached the destination
        if (solve(maze, r + 1, c, path) || solve(maze, r, c + 1, path)) return true;   // explore: down, then right
        path[r][c] = 0;                                           // un-choose: dead end
        return false;
    }

    public static void main(String[] args) {
        int[][] maze = {{1, 0, 0, 0},
                        {1, 1, 0, 1},
                        {0, 1, 0, 0},
                        {0, 1, 1, 1}};
        int n = maze.length;
        int[][] path = new int[n][n];
        if (!solve(maze, 0, 0, path)) { System.out.println("No path exists"); return; }
        System.out.println("path:");
        for (int[] row : path) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) sb.append(j > 0 ? " " : "").append(row[j]);
            System.out.println(sb);
        }
    }
}

JavaScript

function solveMaze(maze) {
    const n = maze.length;
    const path = Array.from({ length: n }, () => Array(n).fill(0));

    function solve(r, c) {
        if (r >= n || c >= n || maze[r][c] === 0) return false;   // off the grid or a wall
        path[r][c] = 1;                                           // choose: step on this cell
        if (r === n - 1 && c === n - 1) return true;              // reached the destination
        if (solve(r + 1, c) || solve(r, c + 1)) return true;      // explore: down first, then right
        path[r][c] = 0;                                           // un-choose: dead end
        return false;
    }

    return solve(0, 0) ? path : null;
}

const maze = [[1, 0, 0, 0],
              [1, 1, 0, 1],
              [0, 1, 0, 0],
              [0, 1, 1, 1]];
const path = solveMaze(maze);
if (path === null) {
    console.log("No path exists");
} else {
    console.log("path:");
    for (const row of path) console.log(row.join(" "));
}

Output

Time O(2^(N²)) worst case — each cell branches two ways · Space O(N²) for the path matrix, O(N) recursion depth

N-Queens problem

Place N queens on an N × N chessboard so that no two queens attack each other — no two share a row, a column or a diagonal. For N = 4 there are exactly two solutions (mirror images of each other).

Approach	Idea	Configurations examined
Super naive	Choose any `N` of the `N²` cells, check each configuration	`C(N², N)` — 1820 for N = 4, ~4.4 × 10⁹ for N = 8
Naive	One queen per row: try every permutation of column numbers, check diagonals	`N!` — 24 for N = 4, 40 320 for N = 8
Backtracking	Place row by row; before placing in `(r, c)` check it against the queens already placed and cut the branch on the first conflict	far fewer — 15 placements tried for N = 4, ~2 000 for N = 8

The first solution found for N = 4

row 0:  . Q . .        cols = [1, 3, 0, 2]
row 1:  . . . Q        row 0 tried col 0 first: rows 1–2 could be filled (0,2,?) but row 3 had no safe
row 2:  Q . . .        column → backtracked all the way to row 0 and moved the first queen to col 1
row 3:  . . Q .

Python

def solve_n_queens(n):
    cols = [-1] * n                     # cols[r] = column of the queen in row r
    solutions = []

    def safe(r, c):
        for pr in range(r):             # compare with every queen already placed
            pc = cols[pr]
            if pc == c or abs(pc - c) == r - pr:      # same column or same diagonal
                return False
        return True

    def place(r):
        if r == n:                      # all rows filled — a solution
            solutions.append(cols[:])
            return
        for c in range(n):
            if safe(r, c):              # prune: skip attacked squares
                cols[r] = c             # choose
                place(r + 1)            # explore
                cols[r] = -1            # un-choose

    place(0)
    return solutions

n = 4
sols = solve_n_queens(n)
for c in sols[0]:
    print(" ".join("Q" if j == c else "." for j in range(n)))
print("solutions:", len(sols))

C++

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

bool safe(const vector<int>& cols, int r, int c) {
    for (int pr = 0; pr < r; pr++) {                     // compare with every queen already placed
        int pc = cols[pr];
        if (pc == c || abs(pc - c) == r - pr) return false;   // same column or same diagonal
    }
    return true;
}

void place(int r, int n, vector<int>& cols, vector<vector<int>>& solutions) {
    if (r == n) { solutions.push_back(cols); return; }   // all rows filled — a solution
    for (int c = 0; c < n; c++) {
        if (!safe(cols, r, c)) continue;                 // prune: skip attacked squares
        cols[r] = c;                                     // choose
        place(r + 1, n, cols, solutions);                // explore
        cols[r] = -1;                                    // un-choose
    }
}

int main() {
    int n = 4;
    vector<int> cols(n, -1);                             // cols[r] = column of the queen in row r
    vector<vector<int>> solutions;
    place(0, n, cols, solutions);
    for (int c : solutions[0]) {
        for (int j = 0; j < n; j++) cout << (j ? " " : "") << (j == c ? "Q" : ".");
        cout << "\n";
    }
    cout << "solutions: " << solutions.size() << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static boolean safe(int[] cols, int r, int c) {
        for (int pr = 0; pr < r; pr++) {                     // compare with every queen already placed
            int pc = cols[pr];
            if (pc == c || Math.abs(pc - c) == r - pr) return false;   // same column or same diagonal
        }
        return true;
    }

    static void place(int r, int n, int[] cols, List<int[]> solutions) {
        if (r == n) { solutions.add(cols.clone()); return; }   // all rows filled — a solution
        for (int c = 0; c < n; c++) {
            if (!safe(cols, r, c)) continue;                 // prune: skip attacked squares
            cols[r] = c;                                     // choose
            place(r + 1, n, cols, solutions);                // explore
            cols[r] = -1;                                    // un-choose
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int[] cols = new int[n];                             // cols[r] = column of the queen in row r
        java.util.Arrays.fill(cols, -1);
        List<int[]> solutions = new ArrayList<>();
        place(0, n, cols, solutions);
        for (int c : solutions.get(0)) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) sb.append(j > 0 ? " " : "").append(j == c ? "Q" : ".");
            System.out.println(sb);
        }
        System.out.println("solutions: " + solutions.size());
    }
}

JavaScript

function solveNQueens(n) {
    const cols = Array(n).fill(-1);          // cols[r] = column of the queen in row r
    const solutions = [];

    function safe(r, c) {
        for (let pr = 0; pr < r; pr++) {     // compare with every queen already placed
            const pc = cols[pr];
            if (pc === c || Math.abs(pc - c) === r - pr) return false;   // same column or same diagonal
        }
        return true;
    }

    function place(r) {
        if (r === n) { solutions.push([...cols]); return; }   // all rows filled — a solution
        for (let c = 0; c < n; c++) {
            if (!safe(r, c)) continue;       // prune: skip attacked squares
            cols[r] = c;                     // choose
            place(r + 1);                    // explore
            cols[r] = -1;                    // un-choose
        }
    }

    place(0);
    return solutions;
}

const n = 4;
const sols = solveNQueens(n);
for (const c of sols[0])
    console.log(Array.from({ length: n }, (_, j) => (j === c ? "Q" : ".")).join(" "));
console.log("solutions:", sols.length);

Output

. Q . .
. . . Q
Q . . .
. . Q .
solutions: 2

Time O(N!) worst case (with pruning far fewer nodes are visited); O(N) per safety check · Space O(N) for cols and the recursion

Sudoku solver

Fill the empty cells (0) of a 9 × 9 grid with digits 1–9 so that every row, every column and every 3 × 3 sub-grid contains each digit exactly once.

Distinct rows — a digit appears at most once in board[row][*].
Distinct columns — a digit appears at most once in board[*][col].
Distinct sub-grids — the 3 × 3 box starting at (row − row % 3, col − col % 3) has no repeats.

Find an empty cell
Scan row-major for the first 0. None left → solved, return true.
Try each digit 1–9
isSafe(row, col, d) checks the row, the column and the 3 × 3 box.
Choose & explore
board[row][col] = d; if solve() returns true, propagate the success.
Un-choose
Otherwise board[row][col] = 0. After all nine digits fail, return false.

Python

def is_safe(board, row, col, d):
    for x in range(9):
        if board[row][x] == d or board[x][col] == d:     # same row or same column
            return False
    r0, c0 = row - row % 3, col - col % 3                # top-left corner of the 3×3 box
    for i in range(3):
        for j in range(3):
            if board[r0 + i][c0 + j] == d:
                return False
    return True

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:                     # first empty cell
                for d in range(1, 10):
                    if is_safe(board, row, col, d):
                        board[row][col] = d              # choose
                        if solve(board):                 # explore
                            return True
                        board[row][col] = 0              # un-choose
                return False                             # no digit fits here → backtrack
    return True                                          # no empty cell left — solved

board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
         [6, 0, 0, 1, 9, 5, 0, 0, 0],
         [0, 9, 8, 0, 0, 0, 0, 6, 0],
         [8, 0, 0, 0, 6, 0, 0, 0, 3],
         [4, 0, 0, 8, 0, 3, 0, 0, 1],
         [7, 0, 0, 0, 2, 0, 0, 0, 6],
         [0, 6, 0, 0, 0, 0, 2, 8, 0],
         [0, 0, 0, 4, 1, 9, 0, 0, 5],
         [0, 0, 0, 0, 8, 0, 0, 7, 9]]
if solve(board):
    for row in board:
        print(" ".join(map(str, row)))
else:
    print("No solution exists")

C++

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(const vector<vector<int>>& b, int row, int col, int d) {
    for (int x = 0; x < 9; x++)
        if (b[row][x] == d || b[x][col] == d) return false;   // same row or same column
    int r0 = row - row % 3, c0 = col - col % 3;               // top-left corner of the 3×3 box
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (b[r0 + i][c0 + j] == d) return false;
    return true;
}

bool solve(vector<vector<int>>& b) {
    for (int row = 0; row < 9; row++)
        for (int col = 0; col < 9; col++)
            if (b[row][col] == 0) {                           // first empty cell
                for (int d = 1; d <= 9; d++)
                    if (isSafe(b, row, col, d)) {
                        b[row][col] = d;                      // choose
                        if (solve(b)) return true;            // explore
                        b[row][col] = 0;                      // un-choose
                    }
                return false;                                 // no digit fits here → backtrack
            }
    return true;                                              // no empty cell left — solved
}

int main() {
    vector<vector<int>> board = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
                                 {6, 0, 0, 1, 9, 5, 0, 0, 0},
                                 {0, 9, 8, 0, 0, 0, 0, 6, 0},
                                 {8, 0, 0, 0, 6, 0, 0, 0, 3},
                                 {4, 0, 0, 8, 0, 3, 0, 0, 1},
                                 {7, 0, 0, 0, 2, 0, 0, 0, 6},
                                 {0, 6, 0, 0, 0, 0, 2, 8, 0},
                                 {0, 0, 0, 4, 1, 9, 0, 0, 5},
                                 {0, 0, 0, 0, 8, 0, 0, 7, 9}};
    if (!solve(board)) { cout << "No solution exists\n"; return 0; }
    for (auto& row : board) {
        for (int j = 0; j < 9; j++) cout << (j ? " " : "") << row[j];
        cout << "\n";
    }
}

Java

public class Main {
    static boolean isSafe(int[][] b, int row, int col, int d) {
        for (int x = 0; x < 9; x++)
            if (b[row][x] == d || b[x][col] == d) return false;   // same row or same column
        int r0 = row - row % 3, c0 = col - col % 3;               // top-left corner of the 3×3 box
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (b[r0 + i][c0 + j] == d) return false;
        return true;
    }

    static boolean solve(int[][] b) {
        for (int row = 0; row < 9; row++)
            for (int col = 0; col < 9; col++)
                if (b[row][col] == 0) {                           // first empty cell
                    for (int d = 1; d <= 9; d++)
                        if (isSafe(b, row, col, d)) {
                            b[row][col] = d;                      // choose
                            if (solve(b)) return true;            // explore
                            b[row][col] = 0;                      // un-choose
                        }
                    return false;                                 // no digit fits here → backtrack
                }
        return true;                                              // no empty cell left — solved
    }

    public static void main(String[] args) {
        int[][] board = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
                         {6, 0, 0, 1, 9, 5, 0, 0, 0},
                         {0, 9, 8, 0, 0, 0, 0, 6, 0},
                         {8, 0, 0, 0, 6, 0, 0, 0, 3},
                         {4, 0, 0, 8, 0, 3, 0, 0, 1},
                         {7, 0, 0, 0, 2, 0, 0, 0, 6},
                         {0, 6, 0, 0, 0, 0, 2, 8, 0},
                         {0, 0, 0, 4, 1, 9, 0, 0, 5},
                         {0, 0, 0, 0, 8, 0, 0, 7, 9}};
        if (!solve(board)) { System.out.println("No solution exists"); return; }
        for (int[] row : board) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 9; j++) sb.append(j > 0 ? " " : "").append(row[j]);
            System.out.println(sb);
        }
    }
}

JavaScript

function isSafe(b, row, col, d) {
    for (let x = 0; x < 9; x++)
        if (b[row][x] === d || b[x][col] === d) return false;   // same row or same column
    const r0 = row - row % 3, c0 = col - col % 3;               // top-left corner of the 3×3 box
    for (let i = 0; i < 3; i++)
        for (let j = 0; j < 3; j++)
            if (b[r0 + i][c0 + j] === d) return false;
    return true;
}

function solve(b) {
    for (let row = 0; row < 9; row++)
        for (let col = 0; col < 9; col++)
            if (b[row][col] === 0) {                            // first empty cell
                for (let d = 1; d <= 9; d++)
                    if (isSafe(b, row, col, d)) {
                        b[row][col] = d;                        // choose
                        if (solve(b)) return true;              // explore
                        b[row][col] = 0;                        // un-choose
                    }
                return false;                                   // no digit fits here → backtrack
            }
    return true;                                                // no empty cell left — solved
}

const board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
               [6, 0, 0, 1, 9, 5, 0, 0, 0],
               [0, 9, 8, 0, 0, 0, 0, 6, 0],
               [8, 0, 0, 0, 6, 0, 0, 0, 3],
               [4, 0, 0, 8, 0, 3, 0, 0, 1],
               [7, 0, 0, 0, 2, 0, 0, 0, 6],
               [0, 6, 0, 0, 0, 0, 2, 8, 0],
               [0, 0, 0, 4, 1, 9, 0, 0, 5],
               [0, 0, 0, 0, 8, 0, 0, 7, 9]];
if (!solve(board)) console.log("No solution exists");
else for (const row of board) console.log(row.join(" "));

Output

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Time O(9^m) worst case for m empty cells — pruning makes real puzzles fast · Space O(m) recursion depth

Interview Q&A

What is the difference between backtracking and plain recursion?

When is backtracking the right tool, and when is DP?

Why must the state be restored exactly after the recursive call?

How would you print all solutions of N-Queens rather than the first one?

What is the time complexity of backtracking for N-Queens?