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 C++ 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
void backtrack(vector<int>& nums, vector<int>& cur, vector<bool>& used, vector<vector<int>>& res){
    if (cur.size() == nums.size()){
        res.push_back(cur);
        return;
    }
    for (int i = 0; i < (int)nums.size(); ++i){
        if (used[i]) continue;
        used[i] = true;
        cur.push_back(nums[i]);
        backtrack(nums, cur, used, res);
        cur.pop_back();
        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 (avoid duplicates by sorting + skip used duplicates)
void backtrack(vector<int>& nums, vector<int>& cur, vector<bool>& used, vector<vector<int>>& res){
    if (cur.size() == nums.size()){
        res.push_back(cur);
        return;
    }
    for (int i = 0; i < (int)nums.size(); ++i){
        // Skip if already used, or if duplicate and previous duplicate not used
        if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
        used[i] = true;
        cur.push_back(nums[i]);
        backtrack(nums, cur, used, res);
        cur.pop_back();
        used[i] = false;
    }
}

// Call with sorted array
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> cur;
    vector<bool> used(nums.size(), false);
    backtrack(nums, cur, used, 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)
void backtrack(int start, int n, int k, vector<int>& cur, vector<vector<int>>& res){
    if (cur.size() == k){
        res.push_back(cur);
        return;
    }
    // Only consider elements from start onwards to avoid duplicates
    for (int i = start; i <= n; ++i){
        cur.push_back(i);
        backtrack(i+1, n, k, cur, res);  // Next start is i+1
        cur.pop_back();
    }
}

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
void backtrack(int start, vector<int>& nums, vector<int>& cur, vector<vector<int>>& res){
    res.push_back(cur);  // Add current subset (including empty set)
    for (int i = start; i < (int)nums.size(); ++i){
        cur.push_back(nums[i]);
        backtrack(i+1, nums, cur, res);
        cur.pop_back();
    }
}

Subsets with duplicates

Sort first, then skip duplicates at the same level.

// Subsets with duplicates (sort first, skip duplicates at same level)
void backtrack(int start, vector<int>& nums, vector<int>& cur, vector<vector<int>>& res){
    res.push_back(cur);
    for (int i = start; i < (int)nums.size(); ++i){
        // Skip duplicates at the same level
        if (i > start && nums[i] == nums[i-1]) continue;
        cur.push_back(nums[i]);
        backtrack(i+1, nums, cur, res);
        cur.pop_back();
    }
}

// Call with sorted array
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(0, nums, cur, 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)
void backtrack(int start, vector<int>& candidates, int target, vector<int>& cur, vector<vector<int>>& res){
    if (target == 0){
        res.push_back(cur);
        return;
    }
    if (target < 0) return;  // Pruning: target exceeded
    
    for (int i = start; i < (int)candidates.size(); ++i){
        cur.push_back(candidates[i]);
        // Can reuse: start=i (not i+1)
        backtrack(i, candidates, target - candidates[i], cur, res);
        cur.pop_back();
    }
}

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

// Combination Sum II (each element used once, duplicates exist)
void backtrack(int start, vector<int>& candidates, int target, vector<int>& cur, vector<vector<int>>& res){
    if (target == 0){
        res.push_back(cur);
        return;
    }
    if (target < 0) return;
    
    for (int i = start; i < (int)candidates.size(); ++i){
        // Skip duplicates at the same level
        if (i > start && candidates[i] == candidates[i-1]) continue;
        cur.push_back(candidates[i]);
        // No reuse: start=i+1
        backtrack(i+1, candidates, target - candidates[i], cur, res);
        cur.pop_back();
    }
}

// Call with sorted array
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(0, candidates, target, cur, 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
void backtrack(int start, int k, int n, vector<int>& cur, vector<vector<int>>& res){
    if (cur.size() == k && n == 0){
        res.push_back(cur);
        return;
    }
    if (cur.size() >= k || n < 0) return;
    
    for (int i = start; i <= 9; ++i){
        cur.push_back(i);
        backtrack(i+1, k, n-i, cur, res);
        cur.pop_back();
    }
}
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
bool dfs(vector<vector<char>>& board, int i, int j, string& word, int idx){
    if (idx == (int)word.size()) return true;
    if (i < 0 || i >= (int)board.size() || j < 0 || j >= (int)board[0].size()) return false;
    if (board[i][j] != word[idx]) return false;
    
    char temp = board[i][j];
    board[i][j] = '#';  // Mark as visited
    
    int dirs[4][2] = \{\{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0\}\};
    for (auto& d : dirs){
        if (dfs(board, i+d[0], j+d[1], word, idx+1)) return true;
    }
    
    board[i][j] = temp;  // Backtrack: restore original value
    return false;
}

bool exist(vector<vector<char>>& board, string word) {
    for (int i = 0; i < (int)board.size(); ++i){
        for (int j = 0; j < (int)board[0].size(); ++j){
            if (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
void backtrack(int row, int n, vector<string>& board, vector<vector<string>>& res){
    if (row == n){
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; ++col){
        if (isValid(board, row, col, n)){
            board[row][col] = 'Q';
            backtrack(row+1, n, board, res);
            board[row][col] = '.';  // Backtrack
        }
    }
}

bool isValid(vector<string>& board, int row, int col, int n){
    // Check column above
    for (int i = 0; i < row; ++i) 
        if (board[i][col] == 'Q') return false;
    
    // Check diagonal \ (top-left to bottom-right)
    for (int i = row-1, j = col-1; i >= 0 && j >= 0; --i, --j)
        if (board[i][j] == 'Q') return false;
    
    // Check diagonal / (top-right to bottom-left)
    for (int i = row-1, j = col+1; i >= 0 && j < n; --i, ++j)
        if (board[i][j] == 'Q') return false;
    
    return true;
}

Sudoku Solver

// Sudoku Solver
bool solveSudoku(vector<vector<char>>& board){
    for (int i = 0; i < 9; ++i){
        for (int j = 0; j < 9; ++j){
            if (board[i][j] == '.'){
                for (char c = '1'; c <= '9'; ++c){
                    if (isValid(board, i, j, c)){
                        board[i][j] = c;
                        if (solveSudoku(board)) return true;
                        board[i][j] = '.';  // Backtrack
                    }
                }
                return false;  // No valid number found
            }
        }
    }
    return true;  // All cells filled
}

bool isValid(vector<vector<char>>& board, int row, int col, char c){
    for (int i = 0; i < 9; ++i){
        // Check row
        if (board[row][i] == c) return false;
        // Check column
        if (board[i][col] == c) return false;
        // Check 3x3 box
        if (board[3*(row/3) + i/3][3*(col/3) + i%3] == c) 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
void backtrack(int start, string& s, vector<string>& cur, vector<vector<string>>& res){
    if (start == (int)s.size()){
        res.push_back(cur);
        return;
    }
    for (int end = start; end < (int)s.size(); ++end){
        if (isPalindrome(s, start, end)){
            cur.push_back(s.substr(start, end-start+1));
            backtrack(end+1, s, cur, res);
            cur.pop_back();  // Backtrack
        }
    }
}

bool isPalindrome(string& s, int l, int r){
    while (l < r) {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}

Optimization: Precompute palindrome table to avoid repeated checks.

// Optimized: Precompute palindrome table
vector<vector<bool>> precomputePalindromes(string& s){
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    for (int i = n-1; i >= 0; --i){
        for (int j = i; j < n; ++j){
            if (i == j) dp[i][j] = true;
            else if (j == i+1) dp[i][j] = (s[i] == s[j]);
            else dp[i][j] = (s[i] == s[j] && 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
void backtrack(int n, int open, int close, string path, vector<string>& res){
    if(path.size() == 2 * n){
        res.push_back(path);
        return;
    }
    if(open < n){
        path.push_back('(');
        backtrack(n, open + 1, close, path, res);
        path.pop_back();
    }
    if(close < open){
        path.push_back(')');
        backtrack(n, open, close + 1, path, res);
        path.pop_back();
    }
}

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

void backtrack(state, constraints, current_solution, results){
    // Base case: solution is complete
    if (isComplete(current_solution)){
        results.add(current_solution);
        return;
    }
    
    // Generate candidates
    for (each candidate in candidates){
        // Pruning: skip invalid candidates early
        if (isValid(candidate, constraints)){
            // Make move: add candidate to solution
            makeMove(candidate, current_solution);
            
            // Recurse: explore further
            backtrack(updated_state, constraints, current_solution, results);
            
            // Backtrack: remove candidate to try next option
            undoMove(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