Backtracking: Practice Problems with Full Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Backtracking: Complete Guide with Pruning Techniques

Welcome to the practice problems for backtracking. If you need a refresher on the code, the code templates have the patterns in all six languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Letter Case Permutation introduces the choice-at-each-step pattern in its simplest form. Master this before adding complexity like tracking used elements or navigating grids.
Subsets teaches the start index pattern that prevents duplicate permutations when order does not matter.
Permutations adds the used array, which is necessary when every element must be used exactly once.
Combinations layers a depth constraint on top of the subset pattern.
Word Search extends backtracking to two dimensions with temporary state modification.
Generate Parentheses demonstrates constraint-based pruning with multiple counters.
Sudoku Solver combines multiple constraint checks into a single search on a 2D grid.
N-Queens II introduces diagonal constraint tracking using sets or boolean arrays.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy

1. Letter Case Permutation

LeetCode 784 | Difficulty: Easy

Brief: Given a string, return all possible strings you can create by transforming each letter individually to lowercase or uppercase.
Why this pattern?: Each character position offers a binary choice: leave digits as they are, or flip a letter between lowercase and uppercase. This is the simplest form of backtracking where every position has a fixed set of alternatives.
Key Insight: Digits are deterministic, so they just extend the string without branching. Letters create exactly two branches, which makes this a clean binary decision tree.

Visual:

    graph TD
    Root["'a1b'"] --> L["'a1b'"]
    Root --> U["'A1b'"]
    L --> LL["'a1b'"]
    L --> LU["'a1B'"]
    U --> UL["'A1b'"]
    U --> UU["'A1B'"]

Code:

var letterCasePermutation = function(s) {
    const result = [];

    function backtrack(i, current) {
        if (i === s.length) {
            result.push(current);
            return;
        }
        const char = s[i];
        if (/\d/.test(char)) {
            backtrack(i + 1, current + char);
        } else {
            backtrack(i + 1, current + char.toLowerCase());
            backtrack(i + 1, current + char.toUpperCase());
        }
    }

    backtrack(0, "");
    return result;
};

def letterCasePermutation(s):
    result = []

    def backtrack(i, current):
        if i == len(s):
            result.append(current)
            return
        char = s[i]
        if char.isdigit():
            backtrack(i + 1, current + char)
        else:
            backtrack(i + 1, current + char.lower())
            backtrack(i + 1, current + char.upper())

    backtrack(0, "")
    return result

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, "", result);
        return result;
    }

    private void backtrack(String s, int i, String current, List<String> result) {
        if (i == s.length()) {
            result.add(current);
            return;
        }
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            backtrack(s, i + 1, current + c, result);
        } else {
            backtrack(s, i + 1, current + Character.toLowerCase(c), result);
            backtrack(s, i + 1, current + Character.toUpperCase(c), result);
        }
    }
}

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> result;
        backtrack(s, 0, "", result);
        return result;
    }

    void backtrack(string& s, int i, string current, vector<string>& result) {
        if (i == s.length()) {
            result.push_back(current);
            return;
        }
        char c = s[i];
        if (isdigit(c)) {
            backtrack(s, i + 1, current + c, result);
        } else {
            backtrack(s, i + 1, current + (char)tolower(c), result);
            backtrack(s, i + 1, current + (char)toupper(c), result);
        }
    }
};

func letterCasePermutation(s string) []string {
    var result []string
    var backtrack func(int, string)
    backtrack = func(i int, current string) {
        if i == len(s) {
            result = append(result, current)
            return
        }
        c := s[i]
        if unicode.IsDigit(rune(c)) {
            backtrack(i+1, current+string(c))
        } else {
            backtrack(i+1, current+string(unicode.ToLower(rune(c))))
            backtrack(i+1, current+string(unicode.ToUpper(rune(c))))
        }
    }
    backtrack(0, "")
    return result
}

def letter_case_permutation(s)
    result = []
    backtrack = ->(i, current) do
        if i == s.length
            result << current
            return
        end
        char = s[i]
        if char =~ /\d/
            backtrack.call(i + 1, current + char)
        else
            backtrack.call(i + 1, current + char.downcase)
            backtrack.call(i + 1, current + char.upcase)
        end
    end
    backtrack.call(0, "")
    result
end

The decision tree has at most 2^L leaves where L is the number of letters, so the time complexity is

O(2^L)

. Each leaf corresponds to one completed string, and the recursion depth never exceeds the original string length, so the space is

O(N)

Medium

2. Permutations

LeetCode 46 | Difficulty: Medium

Brief: Given an array of distinct integers, return all possible permutations in any order.
Why this pattern?: You need to explore every possible ordering. Since you must use every element exactly once, this is a classic ordering backtracking problem.
Key Insight: Use a used array or hash set to keep track of elements already in your current path so you do not pick the same number twice.

Visual:

    graph TD
    Root["[]"] --> A["[1]"]
    Root --> B["[2]"]
    Root --> C["[3]"]
    A --> A1["[1,2]"]
    A --> A2["[1,3]"]
    A1 --> A11["[1,2,3]"]
    A2 --> A21["[1,3,2]"]
    style Root fill:#f9f,stroke:#333,stroke-width:2px

Code:

function permute(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);

    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(nums[i]);
            backtrack(current);
            current.pop();
            used[i] = false;
        }
    }
    backtrack([]);
    return result;
}

def permute(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return result

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] used) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(nums[i]);
            backtrack(result, current, nums, used);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> used(nums.size(), false);
        backtrack(result, current, nums, used);
        return result;
    }

    void backtrack(vector<vector<int>>& result, vector<int>& current, vector<int>& nums, vector<bool>& used) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(result, current, nums, used);
            current.pop_back();
            used[i] = false;
        }
    }
};

func permute(nums []int) [][]int {
    var result [][]int
    used := make([]bool, len(nums))
    var backtrack func([]int)
    backtrack = func(current []int) {
        if len(current) == len(nums) {
            temp := make([]int, len(current))
            copy(temp, current)
            result = append(result, temp)
            return
        }
        for i, u := range used {
            if u { continue }
            used[i] = true
            backtrack(append(current, nums[i]))
            used[i] = false
        }
    }
    backtrack([]int{})
    return result
}

def permute(nums)
  result = []
  used = Array.new(nums.length, false)

  backtrack = ->(current) do
    if current.length == nums.length
      result << current.dup
      return
    end

    nums.each_with_index do |num, i|
      next if used[i]
      used[i] = true
      current << num
      backtrack.call(current)
      current.pop
      used[i] = false
    end
  end

  backtrack.call([])
  result
end

3. Subsets

LeetCode 78 | Difficulty: Medium

Brief: Given an array of unique elements, return all possible subsets (the power set).
Why this pattern?: Every element has two choices: either it is included in the current subset or it is excluded.
Key Insight: To avoid duplicate sets when order does not matter, always iterate from a start index and only look forward.

Visual:

    graph TD
    Root["[]"] --> A["[1]"]
    Root --> B["[2]"]
    Root --> C["[3]"]
    A --> AB["[1,2]"]
    A --> AC["[1,3]"]
    AB --> ABC["[1,2,3]"]
    B --> BC["[2,3]"]

Code:

function subsets(nums) {
    const result = [];
    function backtrack(start, current) {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(0, []);
    return result;
}

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 0, nums);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int start, int[] nums) {
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(result, current, i + 1, nums);
            current.remove(current.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(result, current, 0, nums);
        return result;
    }

    void backtrack(vector<vector<int>>& result, vector<int>& current, int start, vector<int>& nums) {
        result.push_back(current);
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(result, current, i + 1, nums);
            current.pop_back();
        }
    }
};

func subsets(nums []int) [][]int {
    var result [][]int
    var backtrack func(int, []int)
    backtrack = func(start int, current []int) {
        temp := make([]int, len(current))
        copy(temp, current)
        result = append(result, temp)
        for i := start; i < len(nums); i++ {
            backtrack(i+1, append(current, nums[i]))
        }
    }
    backtrack(0, []int{})
    return result
}

4. Combinations

LeetCode 77 | Difficulty: Medium

Brief: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Why this pattern?: This is a direct subset problem with a depth constraint that stops at length k.
Key Insight: You can prune branches earlier if there are not enough remaining numbers to reach length k.

Visual:

    graph TD
    Root["[]"] --> A["[1]"]
    Root --> B["[2]"]
    Root --> C["[3]"]
    A --> AB["[1,2]"]
    A --> AC["[1,3]"]
    B --> BC["[2,3]"]
    style AB fill:#f96,stroke:#333,stroke-width:2px
    style AC fill:#f96,stroke:#333,stroke-width:2px
    style BC fill:#f96,stroke:#333,stroke-width:2px

Code:

function combine(n, k) {
    const result = [];
    function backtrack(start, current) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        for (let i = start; i <= n; i++) {
            current.push(i);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(1, []);
    return result;
}

def combine(n, k):
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 1, n, k);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int start, int n, int k) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i <= n; i++) {
            current.add(i);
            backtrack(result, current, i + 1, n, k);
            current.remove(current.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(result, current, 1, n, k);
        return result;
    }

    void backtrack(vector<vector<int>>& result, vector<int>& current, int start, int n, int k) {
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        for (int i = start; i <= n; i++) {
            current.push_back(i);
            backtrack(result, current, i + 1, n, k);
            current.pop_back();
        }
    }
};

func combine(n int, k int) [][]int {
    var result [][]int
    var backtrack func(int, []int)
    backtrack = func(start int, current []int) {
        if len(current) == k {
            temp := make([]int, k)
            copy(temp, current)
            result = append(result, temp)
            return
        }
        for i := start; i <= n; i++ {
            backtrack(i+1, append(current, i))
        }
    }
    backtrack(1, []int{})
    return result
}

5. Word Search

LeetCode 79 | Difficulty: Medium

Brief: Given an m x n grid of characters and a word, return true if the word exists in the grid.
Why this pattern?: You are exploring a 2D plane. Since you cannot reuse the same cell in a single word path, you must mark cells as visited for the duration of the current search and unmark them when you backtrack.
Key Insight: Modifying the original grid (like replacing a character with #) is a space-efficient way to track visited cells without an extra visited matrix.

Visual:

    graph LR
    Cell["(r, c)"] --> Up["(r-1, c)"]
    Cell --> Down["(r+1, c)"]
    Cell --> Left["(r, c-1)"]
    Cell --> Right["(r, c+1)"]
    style Cell fill:#ccf,stroke:#333

Code:

function exist(board, word) {
    const m = board.length, n = board[0].length;

    function dfs(r, c, i) {
        if (i === word.length) return true;
        if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] !== word[i]) return false;

        const temp = board[r][c];
        board[r][c] = '#';

        if (dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1)) {
            return true;
        }

        board[r][c] = temp;
        return false;
    }

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

def exist(board, word):
    m, n = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word): return True
        if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i]:
            return False

        temp = board[r][c]
        board[r][c] = '#'

        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))

        board[r][c] = temp
        return found

    for r in range(m):
        for c in range(n):
            if dfs(r, c, 0): return True

    return False

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(i)) {
            return false;
        }

        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r+1, c, i+1) ||
                       dfs(board, word, r-1, c, i+1) ||
                       dfs(board, word, r, c+1, i+1) ||
                       dfs(board, word, r, c-1, i+1);
        board[r][c] = temp;
        return found;
    }
}

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int r = 0; r < board.size(); r++) {
            for (int c = 0; c < board[0].size(); c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
        if (i == word.size()) return true;
        if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() || board[r][c] != word[i]) {
            return false;
        }

        char temp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(board, word, r+1, c, i+1) ||
                    dfs(board, word, r-1, c, i+1) ||
                    dfs(board, word, r, c+1, i+1) ||
                    dfs(board, word, r, c-1, i+1);
        board[r][c] = temp;
        return found;
    }
};

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(int, int, int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) { return true }
        if r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[i] {
            return false
        }
        temp := board[r][c]
        board[r][c] = '#'
        found := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1)
        board[r][c] = temp
        return found
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if dfs(r, c, 0) { return true }
        }
    }
    return false
}

def exist(board, word)
  m = board.length
  n = board[0].length

  dfs = ->(r, c, i) do
    return true if i == word.length
    return false if r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word[i]

    temp = board[r][c]
    board[r][c] = '#'

    found = dfs.call(r + 1, c, i + 1) ||
            dfs.call(r - 1, c, i + 1) ||
            dfs.call(r, c + 1, i + 1) ||
            dfs.call(r, c - 1, i + 1)

    board[r][c] = temp
    found
  end

  (0...m).each do |r|
    (0...n).each do |c|
      return true if dfs.call(r, c, 0)
    end
  end
  false
end

6. Generate Parentheses

LeetCode 22 | Difficulty: Medium

Brief: Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Why this pattern?: You are building a string character by character. At each position, you can choose ( or ).
Key Insight: The search space is pruned by two rules. Only add ( if current open_count < n. Only add ) if current close_count < open_count.

Visual:

    graph TD
    Start["'' (0,0)"] --> L["'(' (1,0)"]
    L --> LL["'((' (2,0)"]
    L --> LR["'()' (1,1)"]
    LL --> LLR["'(()' (2,1)"]
    style Start fill:#eee

Code:

function generateParenthesis(n) {
    const result = [];
    function backtrack(s, open, close) {
        if (s.length === 2 * n) {
            result.push(s);
            return;
        }
        if (open < n) backtrack(s + "(", open + 1, close);
        if (close < open) backtrack(s + ")", open, close + 1);
    }
    backtrack("", 0, 0);
    return result;
}

def generateParenthesis(n):
    result = []
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open_count < n:
            backtrack(s + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String s, int open, int close, int n) {
        if (s.length() == 2 * n) {
            result.add(s);
            return;
        }
        if (open < n) backtrack(result, s + "(", open + 1, close, n);
        if (close < open) backtrack(result, s + ")", open, close + 1, n);
    }
}

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }

    void backtrack(vector<string>& result, string s, int open, int close, int n) {
        if (s.length() == 2 * n) {
            result.push_back(s);
            return;
        }
        if (open < n) backtrack(result, s + "(", open + 1, close, n);
        if (close < open) backtrack(result, s + ")", open, close + 1, n);
    }
};

func generateParenthesis(n int) []string {
    var result []string
    var backtrack func(string, int, int)
    backtrack = func(s string, open, close int) {
        if len(s) == 2*n {
            result = append(result, s)
            return
        }
        if open < n {
            backtrack(s + "(", open + 1, close)
        }
        if close < open {
            backtrack(s + ")", open, close + 1)
        }
    }
    backtrack("", 0, 0)
    return result
}

Hard

7. Sudoku Solver

LeetCode 37 | Difficulty: Hard

Brief: Write a program to solve a Sudoku puzzle by filling the empty cells.
Why this pattern?: The number of possible configurations is astronomical. Backtracking lets you fill one cell, check if it is currently valid, and only then proceed to the next empty cell.
Key Insight: Upon finding an empty cell (.), try every digit from 1-9. If a digit leads to a solution, return true. Otherwise, reset to . and try the next digit.

Visual:

    graph TD
    A[Empty Cell] --> B[Try 1]
    B -- Valid --> C[Next Cell]
    B -- Invalid --> D[Try 2]
    C -- No path --> B

Code:

function solveSudoku(board) {
    function isValid(row, col, char) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === char) return false;
            if (board[i][col] === char) return false;
            const blockRow = 3 * Math.floor(row / 3) + Math.floor(i / 3);
            const blockCol = 3 * Math.floor(col / 3) + (i % 3);
            if (board[blockRow][blockCol] === char) return false;
        }
        return true;
    }

    function solve() {
        for (let r = 0; r < 9; r++) {
            for (let c = 0; c < 9; c++) {
                if (board[r][c] === '.') {
                    for (let n = 1; n <= 9; n++) {
                        const char = n.toString();
                        if (isValid(r, c, char)) {
                            board[r][c] = char;
                            if (solve()) return true;
                            board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    solve();
}

def solveSudoku(board):
    def is_valid(row, col, char):
        for i in range(9):
            if board[row][i] == char: return False
            if board[i][col] == char: return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == char: return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for char in "123456789":
                        if is_valid(r, c, char):
                            board[r][c] = char
                            if solve(): return True
                            board[r][c] = '.'
                    return False
        return True

    solve()

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    for (char ch = '1'; ch <= '9'; ch++) {
                        if (isValid(board, r, c, ch)) {
                            board[r][c] = ch;
                            if (solve(board)) return true;
                            board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == ch) return false;
            if (board[i][col] == ch) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == ch) return false;
        }
        return true;
    }
}

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }

    bool solve(vector<vector<char>>& board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    for (char ch = '1'; ch <= '9'; ch++) {
                        if (isValid(board, r, c, ch)) {
                            board[r][c] = ch;
                            if (solve(board)) return true;
                            board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == ch) return false;
            if (board[i][col] == ch) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == ch) return false;
        }
        return true;
    }
};

func solveSudoku(board [][]byte) {
    solve(board)
}

func solve(board [][]byte) bool {
    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            if board[r][c] == '.' {
                for ch := byte('1'); ch <= '9'; ch++ {
                    if isValid(board, r, c, ch) {
                        board[r][c] = ch
                        if solve(board) { return true }
                        board[r][c] = '.'
                    }
                }
                return false
            }
        }
    }
    return true
}

func isValid(board [][]byte, row, col int, ch byte) bool {
    for i := 0; i < 9; i++ {
        if board[row][i] == ch { return false }
        if board[i][col] == ch { return false }
        if board[3*(row/3)+i/3][3*(col/3)+i%3] == ch { return false }
    }
    return true
}

def solve_sudoku(board)
  solve = ->() do
    (0...9).each do |r|
      (0...9).each do |c|
        if board[r][c] == '.'
          ('1'..'9').each do |ch|
            if is_valid?(board, r, c, ch)
              board[r][c] = ch
              return true if solve.call
              board[r][c] = '.'
            end
          end
          return false
        end
      end
    end
    true
  end
  solve.call
end

def is_valid?(board, row, col, char)
  (0...9).each do |i|
    return false if board[row][i] == char
    return false if board[i][col] == char
    return false if board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == char
  end
  true
end

8. N-Queens II

LeetCode 52 | Difficulty: Hard

Brief: Return the number of distinct solutions to the N-Queens puzzle.
Why this pattern?: You must place n queens such that no two queens attack each other. This requires checking row, column, and diagonal constraints at every step.
Key Insight: While rows are handled by recursion level, you can use sets or boolean arrays to track which columns and diagonals are already occupied.
- Columns: index c.
- Diagonals (positive slope): r + c.
- Diagonals (negative slope): r - c.

Visual:

    graph TD
    Row0[Row 0] --> Q0["Q at (0,0)"]
    Q0 --> Row1[Row 1]
    Row1 --> Q1["Q at (1,2)"]
    Row1 --> Q2["Q at (1,3)"]
    style Row0 fill:#fcf

Code:

function totalNQueens(n) {
    let count = 0;
    const cols = new Set(), diag1 = new Set(), diag2 = new Set();

    function backtrack(row) {
        if (row === n) {
            count++;
            return;
        }
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;

            cols.add(col);
            diag1.add(row + col);
            diag2.add(row - col);

            backtrack(row + 1);

            cols.delete(col);
            diag1.delete(row + col);
            diag2.delete(row - col);
        }
    }
    backtrack(0);
    return count;
}

def totalNQueens(n):
    count = 0
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)
            backtrack(row + 1)
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0)
    return count

class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        backtrack(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
        return count;
    }
    private void backtrack(int row, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            int id1 = row + col;
            int id2 = row - col + n;
            if (cols[col] || d1[id1] || d2[id2]) continue;
            cols[col] = true; d1[id1] = true; d2[id2] = true;
            backtrack(row + 1, n, cols, d1, d2);
            cols[col] = false; d1[id1] = false; d2[id2] = false;
        }
    }
}

class Solution {
public:
    int count = 0;
    int totalNQueens(int n) {
        vector<bool> cols(n, false), d1(2 * n, false), d2(2 * n, false);
        backtrack(0, n, cols, d1, d2);
        return count;
    }
    void backtrack(int row, int n, vector<bool>& cols, vector<bool>& d1, vector<bool>& d2) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            int id1 = row + col;
            int id2 = row - col + n;
            if (cols[col] || d1[id1] || d2[id2]) continue;
            cols[col] = true; d1[id1] = true; d2[id2] = true;
            backtrack(row + 1, n, cols, d1, d2);
            cols[col] = false; d1[id1] = false; d2[id2] = false;
        }
    }
};

func totalNQueens(n int) int {
    count := 0
    cols, diag1, diag2 := make(map[int]bool), make(map[int]bool), make(map[int]bool)
    var backtrack func(int)
    backtrack = func(row int) {
        if row == n {
            count++
            return
        }
        for col := 0; col < n; col++ {
            if cols[col] || diag1[row+col] || diag2[row-col] { continue }
            cols[col], diag1[row+col], diag2[row-col] = true, true, true
            backtrack(row + 1)
            delete(cols, col)
            delete(diag1, row+col)
            delete(diag2, row-col)
        }
    }
    backtrack(0)
    return count
}

def total_n_queens(n)
  count = 0
  cols, diag1, diag2 = Set.new, Set.new, Set.new

  backtrack = ->(row) do
    if row == n
      count += 1
      return
    end

    (0...n).each do |col|
      if cols.include?(col) || diag1.include?(row + col) || diag2.include?(row - col)
        next
      end

      cols.add(col)
      diag1.add(row + col)
      diag2.add(row - col)
      backtrack.call(row + 1)
      cols.delete(col)
      diag1.delete(row + col)
      diag2.delete(row - col)
    end
  end

  backtrack.call(0)
  count
end

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These eight problems cover the full range of backtracking techniques. Start with the basic choice pattern in Letter Case Permutation, work through the combinatorial problems, and finish with the complex constraint satisfaction in Sudoku and N-Queens. By the end, you should be able to recognize when backtracking applies and reach for the right template.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .