Jul 25, 2025

Backtracking

Overview

Backtracking is depth-first search over a decision tree. Each recursive call represents a partial solution: make one choice, recurse, then undo that choice so the next branch starts from the same state. When recording a solution, append a copy of the current path or board because the original will continue to change.

A 1D problem builds a sequence of choices from an array, string, or list of groups. The recursive state is usually an index such as start plus a mutable curr path. Recurse with i + 1 when each input position may be used once, with i when reuse is allowed, or over every unused value for permutations. Sorting can expose duplicates and allow early termination.

A 2D problem searches or fills a board. The state includes a row and column, or a single cell index converted into coordinates. Mark a cell or update row, column, and region constraints before recursing, then restore them if the branch fails. A path search usually recurses to neighboring cells, while a board-filling problem advances to the next row or cell.

Backtracking is usually exponential because the search tree may contain many combinations. Effective validity checks, duplicate skipping, and early pruning reduce the number of branches explored. Recursion uses space proportional to the maximum decision depth, in addition to any constraint-tracking structures and returned solutions.

Templates

1D backtracking

Keep the current partial solution in curr and use start to describe which choices remain.
When curr is complete, append a copy and return.
Iterate over the available choices, skipping invalid or duplicate choices.
Append the choice, recurse with the correct next index, and pop it afterward.

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

public class OneDimensionalBacktrackingTemplate {
	public List<List<Integer>> combinations(int[] values, int k) {
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> curr = new ArrayList<>();

		backTrack(values, k, 0, curr, res);
		return res;
	}

	private void backTrack(int[] values, int k, int start, List<Integer> curr, List<List<Integer>> res) {
		if (curr.size() == k) {
			res.add(new ArrayList<>(curr));
			return;
		}

		for (int i = start; i < values.length; i++) {
			curr.add(values[i]);
			backTrack(values, k, i + 1, curr, res);
			curr.remove(curr.size() - 1);
		}
	}
}

def combinations(values: list[int], k: int) -> list[list[int]]:
    res = []
    curr = []

    def backTrack(start):
        if len(curr) == k:
            res.append(curr.copy())
            return

        for i in range(start, len(values)):
            curr.append(values[i])
            backTrack(i + 1)
            curr.pop()

    backTrack(0)
    return res

2D backtracking

Convert the current cell index into row and col, and skip cells that are already filled.
If every cell has been processed, return true.
Try each valid choice and update the board and any constraint-tracking state.
Recurse to the next cell; if the branch fails, restore the cell before trying another choice.
For a neighbor-based path search, recurse to valid neighboring coordinates instead of cell + 1.

public class TwoDimensionalBacktrackingTemplate {
	private int R;
	private int C;

	public boolean solve(int[][] board) {
		R = board.length;
		C = board[0].length;
		return backTrack(board, 0);
	}

	private boolean backTrack(int[][] board, int cell) {
		if (cell == R * C) {
			return true;
		}

		int row = cell / C;
		int col = cell % C;
		if (board[row][col] != 0) {
			return backTrack(board, cell + 1);
		}

		for (int choice = 1; choice <= 9; choice++) {
			if (!isValid(board, row, col, choice)) {
				continue;
			}

			board[row][col] = choice;
			if (backTrack(board, cell + 1)) {
				return true;
			}
			board[row][col] = 0;
		}
		return false;
	}

	private boolean isValid(int[][] board, int row, int col, int choice) {
		// Replace with the problem's row, column, and region checks.
		return true;
	}
}

def solve(board: list[list[int]]) -> bool:
    R, C = len(board), len(board[0])

    def is_valid(row, col, choice):
        # Replace with the problem's row, column, and region checks.
        return True

    def backTrack(cell):
        if cell == R * C:
            return True

        row, col = divmod(cell, C)
        if board[row][col] != 0:
            return backTrack(cell + 1)

        for choice in range(1, 10):
            if not is_valid(row, col, choice):
                continue

            board[row][col] = choice
            if backTrack(cell + 1):
                return True
            board[row][col] = 0
        return False

    return backTrack(0)

Problems

78. Subsets

Generate the power set with a binary choice at every index: skip the current number or include it. Record a copy of curr after all N choices have been made, and pop an included number when backtracking.

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

class Solution {
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		int N = nums.length;

		backTrack(nums, 0, N, new ArrayList<>(), res);
		return res;
	}

	private void backTrack(int[] nums, int i, int N, List<Integer> curr, List<List<Integer>> res) {
		if (i == N) {
			res.add(new ArrayList<>(curr));
			return;
		}

		int num = nums[i];
		// do not take current number
		backTrack(nums, i + 1, N, curr, res);
		// take current number
		curr.add(num);
		backTrack(nums, i + 1, N, curr, res);
		curr.remove(curr.size() - 1);
	}
}

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        N = len(nums)

        def backTrack(i, curr):
            if i == N:
                res.append(curr.copy())
                return

            num = nums[i]
            # do not take current number
            backTrack(i+1, curr)
            # take current number
            curr.append(num)
            backTrack(i+1, curr)
            curr.pop()

        backTrack(0, [])
        return res

46. Permutations

Generate every ordering of the distinct values. At each depth, choose a number not in seen, append it to curr, recurse, then remove it from both structures. Creating each length-N result gives O(N × N!) time and O(N) auxiliary space.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
	public List<List<Integer>> permute(int[] nums) {
		// Time complexity: O(N * N!)
		// Space complexity: O(N)
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> curr = new ArrayList<>();
		Set<Integer> seen = new HashSet<>();
		int N = nums.length;

		backTrack(nums, 0, N, curr, seen, res);
		return res;
	}

	private void backTrack(int[] nums, int count, int N, List<Integer> curr, Set<Integer> seen, List<List<Integer>> res) {
		if (count == N) {
			res.add(new ArrayList<>(curr));
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!seen.contains(nums[i])) {
				seen.add(nums[i]);
				curr.add(nums[i]);
				backTrack(nums, count + 1, N, curr, seen, res);
				seen.remove(nums[i]);
				curr.remove(curr.size() - 1);
			}
		}
	}
}

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # Time complexity: O(N*N!)
        # Space complexity: O(N)
        res = []
        curr = []
        seen = set()
        N = len(nums)
        def backTrack(count):
            if count == N:
                res.append(curr.copy())
                return

            for i in range(N):
                if nums[i] not in seen:
                    seen.add(nums[i])
                    curr.append(nums[i])
                    backTrack(count+1)
                    seen.remove(nums[i])
                    curr.pop()

        backTrack(0)
        return res

39. Combination Sum

Choose numbers that total the target, with unlimited reuse. Sort candidates and track a running total; stop the loop when adding the next number would exceed the target. Recurse with the same index so the current number may be selected again.

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

class Solution {
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> curr = new ArrayList<>();

		backTrack(candidates, target, 0, 0, curr, res);
		return res;
	}

	private void backTrack(int[] candidates, int target, int start, int total, List<Integer> curr, List<List<Integer>> res) {
		if (total == target) {
			res.add(new ArrayList<>(curr));
			return;
		}

		for (int i = start; i < candidates.length; i++) {
			int num = candidates[i];
			if (total + num > target) {
				break;
			}

			curr.add(num);
			total += num;
			backTrack(candidates, target, i, total, curr, res);
			curr.remove(curr.size() - 1);
			total -= num;
		}
	}
}

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        curr = []

        def backTrack(start, total):
            if total == target:
                res.append(curr.copy())
                return

            for i in range(start, len(candidates)):
                num = candidates[i]
                if total + num > target:
                    break
                curr.append(num)
                total += num
                backTrack(i, total)
                curr.pop()
                total -= num

        backTrack(0, 0)
        return res

40. Combination Sum II

Choose numbers that total the target, using each candidate at most once. Sort candidates so the search can stop when a number exceeds remaining, and skip equal candidates at the same recursion level to avoid duplicate combinations.

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

class Solution {
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		int N = candidates.length;
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> curr = new ArrayList<>();
		Arrays.sort(candidates);

		backTrack(candidates, N, 0, target, curr, res);
		return res;
	}

	private void backTrack(int[] candidates, int N, int start, int remaining, List<Integer> curr, List<List<Integer>> res) {
		if (remaining == 0) {
			res.add(new ArrayList<>(curr));
			return;
		}

		for (int i = start; i < N; i++) {
			if (i > start && candidates[i] == candidates[i - 1]) {
				continue;
			}

			if (remaining - candidates[i] < 0) {
				break;
			}

			curr.add(candidates[i]);
			backTrack(
				candidates,
				N,
				i + 1,
				remaining - candidates[i],
				curr,
				res
			);
			curr.remove(curr.size() - 1);
		}
	}
}

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        N = len(candidates)
        res = []
        curr = []
        candidates.sort()

        def backTrack(start, remaining):
            if remaining == 0:
                res.append(curr.copy())
                return

            for i in range(start, N):
                # no need to use the same numbers at the same level
                if i > start and candidates[i] == candidates[i-1]:
                    continue

                # if current candidate is too big, no need to explore
                # further using backTrack() and continue for loop.
                if remaining-candidates[i] < 0:
                    break

                curr.append(candidates[i])
                backTrack(i + 1, remaining-candidates[i])
                curr.pop()

        backTrack(0, target)

        return res

22. Generate Parentheses

Generate every valid sequence of n parenthesis pairs. Track how many left and right parentheses have been placed, and prune whenever either count exceeds n or right parentheses outnumber left parentheses. Otherwise, try appending each character and restore curr afterward.

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

class Solution {
	public List<String> generateParenthesis(int n) {
		List<String> res = new ArrayList<>();
		StringBuilder curr = new StringBuilder();

		backTrack(n, 0, 0, curr, res);
		return res;
	}

	private void backTrack(int n, int left, int right, StringBuilder curr, List<String> res) {
		if (left > n || right > n || right > left) {
			return;
		}

		if (left == n && right == n) {
			res.add(curr.toString());
			return;
		}

		curr.append('(');
		backTrack(n, left + 1, right, curr, res);
		curr.deleteCharAt(curr.length() - 1);
		curr.append(')');
		backTrack(n, left, right + 1, curr, res);
		curr.deleteCharAt(curr.length() - 1);
	}
}

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        curr = []

        # how many left and right parenthsis I have placed so far
        def backTrack(left, right):
            if left > n or right > n or right > left:
                return

            if left == n and right == n:
                res.append("".join(curr.copy()))
                return

            curr.append("(")
            backTrack(left+1, right)
            curr.pop()
            curr.append(")")
            backTrack(left, right+1)
            curr.pop()

        backTrack(0, 0)
        return res

79. Word Search

Find whether a word can be formed by adjacent cells without reusing a cell. Start DFS from each matching position, temporarily mark the current cell, and restore it while backtracking.

class Solution {
	private int R;
	private int C;
	private int N;
	private char[][] board;
	private String word;

	public boolean exist(char[][] board, String word) {
		this.R = board.length;
		this.C = board[0].length;
		this.N = word.length();
		this.board = board;
		this.word = word;

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (backTrack(r, c, 0)) {
					return true;
				}
			}
		}

		return false;
	}

	private boolean backTrack(int r, int c, int idx) {
		if (r < 0 || r >= R ||
			c < 0 || c >= C ||
			idx >= N ||
			board[r][c] != word.charAt(idx)) {
			return false;
		}

		if (idx == N - 1) {
			return true;
		}

		board[r][c] = '*';
		boolean left = backTrack(r, c - 1, idx + 1);
		boolean right = backTrack(r, c + 1, idx + 1);
		boolean top = backTrack(r - 1, c, idx + 1);
		boolean bottom = backTrack(r + 1, c, idx + 1);
		board[r][c] = word.charAt(idx);

		return left || right || top || bottom;
	}
}

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        R, C = len(board), len(board[0])
        N = len(word)

        def backTrack(r, c, idx):
            if r < 0 or r >= R or c < 0 or c >= C or idx >= N or board[r][c] != word[idx]:
                return False

            if idx == N-1:
                return True

            board[r][c] = '*'
            left = backTrack(r, c-1, idx+1)
            right = backTrack(r, c+1, idx+1)
            top = backTrack(r-1, c, idx+1)
            bottom = backTrack(r+1, c, idx+1)
            board[r][c] = word[idx]

            return left or right or top or bottom

        for r in range(R):
            for c in range(C):
                if backTrack(r, c, 0):
                    return True

        return False

131. Palindrome Partitioning

Precompute is_pal[left][right] for every substring so backtracking can test each partition choice in constant time. From start, try every palindromic prefix, append it to curr, recurse from its ending position, and pop it afterward.

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

class Solution {
	public List<List<String>> partition(String s) {
		int N = s.length();
		List<List<String>> res = new ArrayList<>();
		List<String> curr = new ArrayList<>();
		boolean[][] isPal = new boolean[N][N];

		for (int length = 1; length <= N; length++) {
			for (int left = 0; left < N - length + 1; left++) {
				int right = length + left - 1;

				if (s.charAt(left) == s.charAt(right) &&
					(length <= 2 || isPal[left + 1][right - 1])) {
					isPal[left][right] = true;
				}
			}
		}

		backTrack(s, 0, N, isPal, curr, res);
		return res;
	}

	private void backTrack(String s, int start, int N, boolean[][] isPal, List<String> curr, List<List<String>> res) {
		if (start == N) {
			res.add(new ArrayList<>(curr));
			return;
		}

		for (int end = start + 1; end <= N; end++) {
			String sCur = s.substring(start, end);
			if (isPal[start][end - 1]) {
				curr.add(sCur);
				backTrack(s, end, N, isPal, curr, res);
				curr.remove(curr.size() - 1);
			}
		}
	}
}

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        N = len(s)
        res = []
        curr = []

        is_pal = [[False] * N for _ in range(N)]

        for length in range(1, 1 + N):
            for left in range(N-length+1):
                right = length + left - 1

                if s[left] == s[right] and (length <= 2 or is_pal[left+1][right-1]):
                    is_pal[left][right] = True

        def backTrack(start):
            if start == N:
                res.append(curr.copy())
                return

            for end in range(start+1, N+1):
                s_cur = s[start:end]
                if is_pal[start][end-1]:
                    curr.append(s_cur)
                    backTrack(end)
                    curr.pop()
        backTrack(0)
        return res

1087. Brace Expansion

Parse the expression into ordered groups of choices. A normal character contributes one choice, while a brace group contributes its sorted options. Backtrack through one group at a time and append each completed string to res.

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

class Solution {
	public String[] expand(String s) {
		List<List<Character>> groups = new ArrayList<>();
		int i = 0;

		while (i < s.length()) {
			if (s.charAt(i) == '{') {
				List<Character> options = new ArrayList<>();
				i += 1;
				while (s.charAt(i) != '}') {
					if (s.charAt(i) != ',') {
						options.add(s.charAt(i));
					}
					i += 1;
				}
				i += 1;
				Collections.sort(options);
				groups.add(options);
			} else {
				groups.add(List.of(s.charAt(i)));
				i += 1;
			}
		}

		List<String> res = new ArrayList<>();
		StringBuilder curr = new StringBuilder();
		int N = groups.size();

		backTrack(groups, N, 0, curr, res);
		return res.toArray(new String[0]);
	}

	private void backTrack(List<List<Character>> groups, int N, int idx, StringBuilder curr, List<String> res) {
		if (idx == N) {
			res.add(curr.toString());
			return;
		}

		for (char c : groups.get(idx)) {
			curr.append(c);
			backTrack(groups, N, idx + 1, curr, res);
			curr.deleteCharAt(curr.length() - 1);
		}
	}
}

from typing import List

class Solution:
    def expand(self, s: str) -> List[str]:
        groups = []
        i = 0

        while i < len(s):
            if s[i] == '{':
                options = []
                i += 1
                while s[i] != '}':
                    if s[i] != ',':
                        options.append(s[i])
                    i += 1
                i += 1
                groups.append(sorted(options))
            else:
                groups.append([s[i]])
                i += 1

        res = []
        curr = []
        N = len(groups)

        def backTrack(idx):
            if idx == N:
                res.append("".join(curr))
                return

            for char in groups[idx]:
                curr.append(char)
                backTrack(idx+1)
                curr.pop()

        backTrack(0)
        return res

51. N-Queens

Place exactly one queen in each row. Track occupied columns, descending diagonals with row - col + n - 1, and ascending diagonals with row + col. After placing a queen, mark all three constraints, recurse to the next row, then remove the queen and restore the status arrays.

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

class Solution {
	private int n;
	private List<List<String>> res;
	private List<int[]> currQueens;
	private boolean[] colStatus;
	private boolean[] diag1Status;
	private boolean[] diag2Status;

	public List<List<String>> solveNQueens(int n) {
		this.n = n;
		res = new ArrayList<>();
		currQueens = new ArrayList<>();
		colStatus = new boolean[n];
		diag1Status = new boolean[2 * n - 1];
		diag2Status = new boolean[2 * n - 1];

		backTrack(0);
		return res;
	}

	private void backTrack(int row) {
		if (row == n) {
			res.add(drawBoard(currQueens));
			return;
		}

		for (int col = 0; col < n; col++) {
			if (colStatus[col] == false &&
				diag1Status[row - col + n - 1] == false &&
				diag2Status[row + col] == false) {
				currQueens.add(new int[] {row, col});
				colStatus[col] = true;
				diag1Status[row - col + n - 1] = true;
				diag2Status[row + col] = true;
				backTrack(row + 1);
				currQueens.remove(currQueens.size() - 1);
				colStatus[col] = false;
				diag1Status[row - col + n - 1] = false;
				diag2Status[row + col] = false;
			}
		}
	}

	private List<String> drawBoard(List<int[]> queens) {
		int N = queens.size();
		char[][] board = new char[N][N];
		for (char[] row : board) {
			Arrays.fill(row, '.');
		}
		for (int[] queen : queens) {
			int r = queen[0];
			int c = queen[1];
			board[r][c] = 'Q';
		}

		List<String> result = new ArrayList<>();
		for (char[] row : board) {
			result.add(new String(row));
		}
		return result;
	}
}

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        curr_queens = []
        col_status = [False] * n
        diag1_status = [False] * (2*n - 1)
        diag2_status = [False] * (2*n - 1)

        def backTrack(row):
            if row == n:
                res.append(self.drawBoard(curr_queens))
                return

            for col in range(n):
                if col_status[col] == False and diag1_status[row-col+n-1] == False and diag2_status[row+col] == False:
                    curr_queens.append((row, col))
                    col_status[col] = True
                    diag1_status[row-col+n-1] = True
                    diag2_status[row+col] = True
                    backTrack(row+1)
                    curr_queens.pop()
                    col_status[col] = False
                    diag1_status[row-col+n-1] = False
                    diag2_status[row+col] = False

        backTrack(0)

        return res

    def drawBoard(self, queens):
        N = len(queens)
        board = [["."]*N for _ in range(N)]
        for r, c in queens:
            board[r][c] = "Q"
        return ["".join(row) for row in board]

37. Sudoku Solver

Preprocess the board into row, column, and box occupancy tables. Traverse cells from left to right and top to bottom, skipping filled cells. For an empty cell, try each valid digit, update all three tables, recurse, and restore the cell and tables if that choice cannot complete the board.

class Solution {
	public void solveSudoku(char[][] board) {
		int[][] rows = new int[9][10];
		int[][] cols = new int[9][10];
		int[][] boxs = new int[9][10];

		// Pre-processing
		for (int r = 0; r < 9; r++) {
			for (int c = 0; c < 9; c++) {
				char ch = board[r][c];
				if (ch != '.') {
					int n = ch - '0';
					int bx = c / 3;
					int by = r / 3;
					rows[r][n] = 1;
					cols[c][n] = 1;
					boxs[by * 3 + bx][n] = 1;
				}
			}
		}

		fillBoard(board, 0, 0, rows, cols, boxs);
	}

	private boolean fillBoard(char[][] board, int x, int y, int[][] rows, int[][] cols, int[][] boxs) {
		if (y == 9) {
			return true;
		}

		// Compute next coordinates
		int nx = (x + 1) % 9;
		int ny = nx == 0 ? y + 1 : y;

		// Filled at current location, go to next location
		if (board[y][x] != '.') {
			return fillBoard(board, nx, ny, rows, cols, boxs);
		}

		// Try 1-9 one by one
		for (int i = 1; i < 10; i++) {
			int boxKey = (y / 3) * 3 + x / 3;
			if (rows[y][i] == 0 &&
				cols[x][i] == 0 &&
				boxs[boxKey][i] == 0) {
				rows[y][i] = 1;
				cols[x][i] = 1;
				boxs[boxKey][i] = 1;
				board[y][x] = (char) ('0' + i);
				if (fillBoard(board, nx, ny, rows, cols, boxs)) {
					return true;
				}
				rows[y][i] = 0;
				cols[x][i] = 0;
				boxs[boxKey][i] = 0;
				board[y][x] = '.';
			}
		}
		return false;
	}
}

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = [[0]*10 for _ in range(9)]
        cols = [[0]*10 for _ in range(9)]
        boxs = [[0]*10 for _ in range(9)]
        #Pre-processing
        for r in range(9):
            for c in range(9):
                char = board[r][c]
                if char != '.':
                    n = int(char)
                    bx = c//3
                    by = r//3
                    rows[r][n] = 1
                    cols[c][n] = 1
                    boxs[by*3+bx][n] = 1

        def fillBoard(board, x, y):
            if y == 9: return True
            #compute next coordinates
            nx = (x+1)%9
            ny = y+1 if nx==0 else y
            #filled at current location, go to next location
            if board[y][x] != '.': return fillBoard(board, nx, ny)
            #Try 1-9 one by one
            for i in range(1, 10):
                box_key = (y//3)*3 + x//3
                if all((not rows[y][i], not cols[x][i], not boxs[box_key][i])):
                    rows[y][i] = 1
                    cols[x][i] = 1
                    boxs[box_key][i] = 1
                    board[y][x] = str(i)
                    if fillBoard(board, nx, ny):
                        return True
                    rows[y][i] = 0
                    cols[x][i] = 0
                    boxs[box_key][i] = 0
                    board[y][x] = '.'
            return False

        fillBoard(board, 0, 0)