Problems

Develop your intuition for backtracking by solving these curated problems. They are ordered from building basic blocks (Subsets, Permutations) to complex constraint satisfaction (Sudoku, N-Queens).

Before you start, make sure you’ve reviewed the Backtracking Code Templates.

Medium

1. Permutations

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 don’t pick the same number twice.

Visual Explanation:

  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

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

2. Subsets

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 doesn’t matter (like [1,2] vs [2,1]), always iterate from a start index and only look forward.

Visual Explanation:

  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]"]

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
}

def subsets(nums)
  result = []
  backtrack = ->(start, current) do
    result << current.dup
    (start...nums.length).each do |i|
      current << nums[i]
      backtrack.call(i + 1, current)
      current.pop
    end
  end
  backtrack.call(0, [])
  result
end

3. Combinations

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 (length == k).
Key Insight: You can prune branches earlier if there aren’t enough remaining numbers to reach length k.

Visual Explanation:

  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

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
}

def combine(n, k)
  result = []
  backtrack = ->(start, current) do
    if current.length == k
      result << current.dup
      return
    end
    (start..n).each do |i|
      current << i
      backtrack.call(i + 1, current)
      current.pop
    end
  end
  backtrack.call(1, [])
  result
end

4. Word Search

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[m][n] matrix.

Visual Explanation:

  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

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

5. Generate Parentheses

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 index, you can choose ( or ).
Key Insight: The search space is pruned by two rules:
1. Only add ( if current open_count < n.
2. Only add ) if current close_count < open_count.

Visual Explanation:

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

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
}

def generate_parenthesis(n)
  result = []
  backtrack = ->(s, open, close) do
    if s.length == 2 * n
      result << s
      return
    end
    backtrack.call(s + "(", open + 1, close) if open < n
    backtrack.call(s + ")", open, close + 1) if close < open
  end
  backtrack.call("", 0, 0)
  result
end

Hard

6. Sudoku Solver

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 allows us to fill one cell, check if it’s 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 Explanation:

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

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

7. N-Queens II

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 Explanation:

  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

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

Recommended Study Order

Subsets: The simplest form of backtracking (include/exclude choice).
Permutations: Introduces the concept of “used” tracking.
Combinations: Fine-tunes your starting index logic.
Word Search: Mastery of grid-based backtracking and temporary state modification.
Sudoku Solver: Understand complex constraints and optimization.