Welcome to the backtracking templates! Backtracking is one of the most versatile problem-solving techniques in competitive programming—once you learn the core pattern, you can tackle a huge family of problems from permutations to Sudoku. This page gives you battle-tested Python templates for every major backtracking pattern, ready to adapt and submit.

New to Backtracking? Backtracking = DFS + undo. You try a choice, recurse deeper, and if it doesn’t work out, you undo the choice and try the next one. It’s how you systematically explore all possibilities without missing any.

Subsets of [1, 2, 3] — Backtracking Decision Tree { } +1 skip 1 {1} { } +2 skip 2 +2 skip 2 {1,2} {1} {2} { } +3 skip 3 +3 skip 3 +3 skip 3 +3 skip 3 {1,2,3} {1,2} {1,3} {1} {2,3} {2} {3} { } Include element Skip element Leaf = final subset Each root-to-leaf path is one subset · 2³ = 8 subsets total

Contents

Introduction

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning (“backtracking”) partial candidates that cannot lead to valid solutions. It’s essentially a depth-first search with pruning.

Key Characteristics:

  • Builds solutions incrementally
  • Abandons partial solutions that cannot be completed (pruning)
  • Uses recursion to explore the solution space
  • Restores state after recursive calls (backtracking step)

The Backtracking Template — nearly every problem on this page follows this skeleton:

backtrack(current_state):
    if is_solution(current_state):
        record solution
        return
    for each choice in available_choices:
        if is_valid(choice):        ← pruning
            make_choice()
            backtrack(next_state)    ← recurse
            undo_choice()            ← backtrack

Permutations (All Arrangements)

When to use: The problem asks for “all arrangements”, “all orderings”, “every possible order”, or “rearrange”.

Generate all permutations of distinct elements.

Permutation Tree for [1, 2, 3] — pick one unused element per level pick 1 pick 2 pick 3 +2 +3 +1 +3 +1 +2 +3 +2 +3 +1 +2 +1 [ ] [1] [2] [3] [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] Partial path Complete permutation (leaf) 3! = 6 permutations · each root-to-leaf path is one arrangement

Permutations without duplicates

# Permutations without duplicates
def permute_backtrack(nums: list[int], cur: list[int], used: list[bool], res: list[list[int]]) -> None:
    if len(cur) == len(nums):
        res.append(cur.copy())
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        cur.append(nums[i])
        permute_backtrack(nums, cur, used, res)
        cur.pop()
        used[i] = False

Permutations with duplicates

Avoid duplicates by sorting first, then skipping duplicates at the same level when the previous duplicate hasn’t been used.

# Permutations with duplicates (sort first; skip same value at same level if prev unused)
def permute_unique_backtrack(nums: list[int], cur: list[int], used: list[bool], res: list[list[int]]) -> None:
    if len(cur) == len(nums):
        res.append(cur.copy())
        return
    for i in range(len(nums)):
        if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
            continue
        used[i] = True
        cur.append(nums[i])
        permute_unique_backtrack(nums, cur, used, res)
        cur.pop()
        used[i] = False


def permute_unique(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    res: list[list[int]] = []
    permute_unique_backtrack(nums, [], [False] * len(nums), res)
    return res
ID Title Link Solution
46 Permutations Link Solution
47 Permutations II Link Solution

Combinations (Choose k from n)

When to use: The problem says “choose k from n”, “select k items”, or “all groups of size k” where order doesn’t matter.

Generate all combinations of k elements from n elements. Order doesn’t matter, so we use start index to avoid duplicates.

# Combinations C(n, k) — choose k numbers from 1..n
def combine_backtrack(start: int, n: int, k: int, cur: list[int], res: list[list[int]]) -> None:
    if len(cur) == k:
        res.append(cur.copy())
        return
    for i in range(start, n + 1):
        cur.append(i)
        combine_backtrack(i + 1, n, k, cur, res)
        cur.pop()

Key insight: Use start parameter to ensure we only consider elements after the current position, preventing duplicate combinations.

ID Title Link Solution
77 Combinations Link Solution
22 Generate Parentheses Link Solution

Subsets (All Subsets)

When to use: The problem asks for “all subsets”, “power set”, “all subsequences”, or “every possible selection”.

Generate all subsets (power set) of an array. This includes the empty set and the set itself.

Subsets of [1, 2, 3] — Include / Exclude at Each Level incl 1 excl 1 +2 skip 2 +2 skip 2 +3 skip +3 skip +3 skip +3 skip { } {1} { } {1,2} {1} {2} { } {1,2,3} {1,2} {1,3} {1} {2,3} {2} {3} { } Include element Exclude element Each root-to-leaf path is one subset · 2³ = 8 subsets total

Subsets without duplicates

# Subsets without duplicates
def subsets_backtrack(start: int, nums: list[int], cur: list[int], res: list[list[int]]) -> None:
    res.append(cur.copy())
    for i in range(start, len(nums)):
        cur.append(nums[i])
        subsets_backtrack(i + 1, nums, cur, res)
        cur.pop()

Subsets with duplicates

Sort first, then skip duplicates at the same level.

# Subsets with duplicates (sort first, skip duplicates at same level)
def subsets_dup_backtrack(start: int, nums: list[int], cur: list[int], res: list[list[int]]) -> None:
    res.append(cur.copy())
    for i in range(start, len(nums)):
        if i > start and nums[i] == nums[i - 1]:
            continue
        cur.append(nums[i])
        subsets_dup_backtrack(i + 1, nums, cur, res)
        cur.pop()


def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res: list[list[int]] = []
    subsets_dup_backtrack(0, nums, [], res)
    return res
ID Title Link Solution
78 Subsets Link Solution
90 Subsets II Link -

Combination Sum (Unbounded/Reuse Elements)

When to use: The problem asks for “all combinations that sum to target”, “target sum with reuse allowed”, or “find numbers adding to k”.

Find all combinations that sum to target. Elements can be reused or used once depending on the problem.

Combination Sum (can reuse same element)

# Combination Sum (can reuse same element)
def combination_sum_backtrack(
    start: int, candidates: list[int], target: int, cur: list[int], res: list[list[int]]
) -> None:
    if target == 0:
        res.append(cur.copy())
        return
    if target < 0:
        return
    for i in range(start, len(candidates)):
        cur.append(candidates[i])
        combination_sum_backtrack(i, candidates, target - candidates[i], cur, res)
        cur.pop()

Combination Sum II (each element used once, duplicates exist)

# Combination Sum II (each element used once, duplicates exist)
def combination_sum2_backtrack(
    start: int, candidates: list[int], target: int, cur: list[int], res: list[list[int]]
) -> None:
    if target == 0:
        res.append(cur.copy())
        return
    if target < 0:
        return
    for i in range(start, len(candidates)):
        if i > start and candidates[i] == candidates[i - 1]:
            continue
        cur.append(candidates[i])
        combination_sum2_backtrack(i + 1, candidates, target - candidates[i], cur, res)
        cur.pop()


def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res: list[list[int]] = []
    combination_sum2_backtrack(0, candidates, target, [], res)
    return res

Combination Sum III (choose k numbers from 1-9 that sum to n)

# Combination Sum III: choose k numbers from 1-9 that sum to n
def combination_sum3_backtrack(start: int, k: int, n: int, cur: list[int], res: list[list[int]]) -> None:
    if len(cur) == k and n == 0:
        res.append(cur.copy())
        return
    if len(cur) >= k or n < 0:
        return
    for i in range(start, 10):
        cur.append(i)
        combination_sum3_backtrack(i + 1, k, n - i, cur, res)
        cur.pop()
ID Title Link Solution
39 Combination Sum Link -
40 Combination Sum II Link -
216 Combination Sum III Link -

Grid Backtracking (Word Search, Path Finding)

When to use: The problem says “find a path in a grid”, “word search”, “explore all directions”, or involves marking/unmarking visited cells.

Backtrack on 2D grid with constraints. Mark cells as visited during exploration, then restore them.

# Word Search: find if word exists in grid
DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def word_search_dfs(board: list[list[str]], i: int, j: int, word: str, idx: int) -> bool:
    if idx == len(word):
        return True
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
        return False
    if board[i][j] != word[idx]:
        return False
    temp = board[i][j]
    board[i][j] = "#"
    for di, dj in DIRS:
        if word_search_dfs(board, i + di, j + dj, word, idx + 1):
            board[i][j] = temp
            return True
    board[i][j] = temp
    return False


def word_exist(board: list[list[str]], word: str) -> bool:
    for i in range(len(board)):
        for j in range(len(board[0])):
            if word_search_dfs(board, i, j, word, 0):
                return True
    return False

Key points:

  • Mark cell as visited before recursion
  • Restore cell value after recursion (backtracking)
  • Check bounds and constraints before recursing
ID Title Link Solution
79 Word Search Link Solution
212 Word Search II Link -
351 Android Unlock Patterns Link Solution
425 Word Squares Link Solution
489 Robot Room Cleaner Link Solution

Constraint Satisfaction (N-Queens, Sudoku)

When to use: The problem involves “placing items with constraints”, “N-Queens”, “Sudoku”, or “valid placement” where each choice must satisfy multiple rules.

Backtracking with complex constraints. Validate each move before placing.

N-Queens

# N-Queens: place n queens on n×n board (board is list[list[str]])
def n_queens_is_safe(board: list[list[str]], row: int, col: int, n: int) -> bool:
    for i in range(row):
        if board[i][col] == "Q":
            return False
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == "Q":
            return False
        i -= 1
        j -= 1
    i, j = row - 1, col + 1
    while i >= 0 and j < n:
        if board[i][j] == "Q":
            return False
        i -= 1
        j += 1
    return True


def n_queens_backtrack(row: int, n: int, board: list[list[str]], res: list[list[str]]) -> None:
    if row == n:
        res.append(["".join(r) for r in board])
        return
    for col in range(n):
        if n_queens_is_safe(board, row, col, n):
            board[row][col] = "Q"
            n_queens_backtrack(row + 1, n, board, res)
            board[row][col] = "."

Sudoku Solver

# Sudoku Solver (mutates board in place)
def sudoku_valid(board: list[list[str]], row: int, col: int, ch: str) -> bool:
    for i in range(9):
        if board[row][i] == ch:
            return False
        if board[i][col] == ch:
            return False
    br, bc = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == ch:
                return False
    return True


def solve_sudoku(board: list[list[str]]) -> bool:
    for i in range(9):
        for j in range(9):
            if board[i][j] != ".":
                continue
            for d in "123456789":
                if not sudoku_valid(board, i, j, d):
                    continue
                board[i][j] = d
                if solve_sudoku(board):
                    return True
                board[i][j] = "."
            return False
    return True
ID Title Link Solution
51 N-Queens Link Solution
52 N-Queens II Link -
37 Sudoku Solver Link -

Palindrome Partitioning

When to use: The problem asks to “partition a string into palindromes”, “split into palindromic substrings”, or “all ways to cut a string”.

Partition string into palindromic substrings. Check if substring is palindrome before partitioning.

# Palindrome Partitioning
def is_pal_sub(s: str, l: int, r: int) -> bool:
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def partition_backtrack(start: int, s: str, cur: list[str], res: list[list[str]]) -> None:
    if start == len(s):
        res.append(cur.copy())
        return
    for end in range(start, len(s)):
        if is_pal_sub(s, start, end):
            cur.append(s[start : end + 1])
            partition_backtrack(end + 1, s, cur, res)
            cur.pop()

Optimization: Precompute palindrome table to avoid repeated checks.

# Optimized: precompute palindrome table dp[i][j]
def precompute_palindromes(s: str) -> list[list[bool]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if i == j:
                dp[i][j] = True
            elif j == i + 1:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
    return dp
ID Title Link Solution
131 Palindrome Partitioning Link Solution
132 Palindrome Partitioning II Link -
5 Longest Palindromic Substring Link Solution
647 Palindromic Substrings Link Solution

Parentheses Generation

Generate all valid parentheses combinations using backtracking.

# Generate Parentheses: generate all valid n pairs
def gen_parentheses_backtrack(n: int, open_cnt: int, close_cnt: int, path: list[str], res: list[str]) -> None:
    if len(path) == 2 * n:
        res.append("".join(path))
        return
    if open_cnt < n:
        path.append("(")
        gen_parentheses_backtrack(n, open_cnt + 1, close_cnt, path, res)
        path.pop()
    if close_cnt < open_cnt:
        path.append(")")
        gen_parentheses_backtrack(n, open_cnt, close_cnt + 1, path, res)
        path.pop()

Key constraints:

  • open < n: Can add opening parenthesis if not all used
  • close < open: Can add closing parenthesis if there are unmatched openings
  • Base case: path length equals 2 * n
ID Title Link Solution
22 Generate Parentheses Link Solution
1087 Brace Expansion Link Solution

General Backtracking Template

# Sketch — fill in problem-specific helpers
def backtrack_sketch(state, constraints, current_solution, results):
    if is_complete(current_solution):
        results.append(list(current_solution))
        return
    for candidate in iter_candidates(state):
        if not is_valid_move(candidate, constraints):
            continue
        make_move(candidate, current_solution)
        backtrack_sketch(next_state(state, candidate), constraints, current_solution, results)
        undo_move(candidate, current_solution)

Key Points:

  • Base Case: When solution is complete, add to results
  • Pruning: Skip invalid candidates early to reduce search space
  • Make Move: Add candidate to current solution and update state
  • Recurse: Explore further with updated state
  • Backtrack: Remove candidate and restore state to try next option

Common Optimizations:

  1. Early pruning: Check constraints before recursing
  2. Memoization: Cache results for repeated subproblems (if applicable)
  3. Sorting: Sort input to handle duplicates efficiently
  4. Precomputation: Precompute expensive checks (e.g., palindrome table)

Time Complexity: Typically exponential O(2^n) or O(n!) depending on problem Space Complexity: O(depth) for recursion stack + O(solution_size) for current solution

Quick Reference

Pattern Signal # Solutions Time
Permutations “all arrangements”, “ordering” n! O(n × n!)
Combinations “choose k from n” C(n,k) O(C(n,k))
Subsets “all subsets”, “power set” 2^n O(n × 2^n)
Combination Sum “target sum with reuse” varies O(2^n)
Grid “find path in grid” varies O(4^(m×n))
Constraint “N-Queens”, “Sudoku” varies O(n!)

More templates