function backtrack(row, n, cols, diag, antiDiag):
    if row == n:
        add board to result
        return

    for col in 0..n-1:
        if cols[col] || diag[row-col+n] || antiDiag[row+col]:
            continue

        place queen at (row, col)
        backtrack(row+1, n, cols, diag, antiDiag)
        remove queen

Input: Board / configuration Core Idea: Place → validate → recurse → remove Used in: N-Queens, Sudoku

public void solve(int row, int n, boolean[] cols, boolean[] diag, boolean[] antiDiag) {
    if (row == n) {
        count++;
        return;
    }

    for (int col = 0; col < n; col++) {
        if (cols[col] || diag[row - col + n] || antiDiag[row + col])
            continue;

        cols[col] = diag[row - col + n] = antiDiag[row + col] = true;
        solve(row + 1, n, cols, diag, antiDiag);
        cols[col] = diag[row - col + n] = antiDiag[row + col] = false;
    }
}

def solve(row, n, cols, diag, anti_diag):
    if row == n:
        count += 1
        return

    for col in range(n):
        if cols[col] or diag[row - col + n] or anti_diag[row + col]:
            continue
        cols[col] = diag[row - col + n] = anti_diag[row + col] = True
        solve(row + 1, n, cols, diag, anti_diag)
        cols[col] = diag[row - col + n] = anti_diag[row + col] = False

void solve(int row, int n,
           vector<bool>& cols, vector<bool>& diag, vector<bool>& anti) {
    if (row == n) { count++; return; }

    for (int col = 0; col < n; col++) {
        if (cols[col] || diag[row - col + n] || anti[row + col])
            continue;
        cols[col] = diag[row - col + n] = anti[row + col] = true;
        solve(row + 1, n, cols, diag, anti);
        cols[col] = diag[row - col + n] = anti[row + col] = false;
    }
}

function solve(row, n, cols, diag, anti) {
  if (row === n) {
    count++;
    return;
  }
  for (let col = 0; col < n; col++) {
    if (cols[col] || diag[row - col + n] || anti[row + col]) continue;
    cols[col] = diag[row - col + n] = anti[row + col] = true;
    solve(row + 1, n, cols, diag, anti);
    cols[col] = diag[row - col + n] = anti[row + col] = false;
  }
}

function dfs(grid, word, index, r, c):
    if index == word.length:
        return true
    if out of bounds or mismatch or visited:
        return false

    mark visited
    for each direction:
        if dfs(grid, word, index+1, nr, nc):
            return true
    unmark

    return false

Input: Grid + word Core Idea: Explore 4 directions from each cell Used in: Word Search, Rat in Maze

public boolean exist(char[][] board, String word) {
    int n = board.length, m = board[0].length;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (dfs(board, word, 0, i, j))
                return true;

    return false;
}

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

    char temp = board[i][j];
    board[i][j] = '#';

    boolean found = dfs(board, word, idx+1, i+1, j)
                 || dfs(board, word, idx+1, i-1, j)
                 || dfs(board, word, idx+1, i, j+1)
                 || dfs(board, word, idx+1, i, j-1);

    board[i][j] = temp;
    return found;
}

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

    def dfs(idx, i, j):
        if idx == len(word):
            return True
        if not (0 <= i < n and 0 <= j < m) or board[i][j] != word[idx]:
            return False
        temp, board[i][j] = board[i][j], "#"
        found = (dfs(idx + 1, i + 1, j) or dfs(idx + 1, i - 1, j) or
                 dfs(idx + 1, i, j + 1) or dfs(idx + 1, i, j - 1))
        board[i][j] = temp
        return found

    return any(dfs(0, i, j) for i in range(n) for j in range(m))

bool dfs(vector<vector<char>>& b, const string& w, int idx, int i, int j) {
    if (idx == (int)w.size()) return true;
    int n = b.size(), m = b[0].size();
    if (i < 0 || j < 0 || i >= n || j >= m || b[i][j] != w[idx])
        return false;

    char temp = b[i][j];
    b[i][j] = '#';
    bool found = dfs(b,w,idx+1,i+1,j) || dfs(b,w,idx+1,i-1,j)
              || dfs(b,w,idx+1,i,j+1) || dfs(b,w,idx+1,i,j-1);
    b[i][j] = temp;
    return found;
}

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, word, 0, i, j)) return true;
    return false;
}

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

  function dfs(idx, i, j) {
    if (idx === word.length) return true;
    if (i < 0 || j < 0 || i >= n || j >= m ||
        board[i][j] !== word[idx]) return false;
    const temp = board[i][j];
    board[i][j] = "#";
    const found =
      dfs(idx + 1, i + 1, j) || dfs(idx + 1, i - 1, j) ||
      dfs(idx + 1, i, j + 1) || dfs(idx + 1, i, j - 1);
    board[i][j] = temp;
    return found;
  }

  for (let i = 0; i < n; i++)
    for (let j = 0; j < m; j++) if (dfs(0, i, j)) return true;
  return false;
}

function backtrack(index, path, nums):
    add copy of path to result

    for i from index to n-1:
        if i > index && nums[i] == nums[i-1]:
            continue    // skip duplicates

        path.add(nums[i])
        backtrack(i+1, path, nums)
        path.removeLast()

Input: Array (may contain duplicates) Core Idea: Sort + skip consecutive duplicates Used in: Subsets II, Combination Sum II

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int idx, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));

    for (int i = idx; i < nums.length; i++) {
        if (i > idx && nums[i] == nums[i-1]) continue;

        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

def subsets_with_dup(nums):
    nums.sort()
    res, path = [], []

    def backtrack(idx):
        res.append(path[:])
        for i in range(idx, len(nums)):
            if i > idx and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

void backtrack(vector<int>& nums, int idx,
               vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = idx; i < (int)nums.size(); i++) {
        if (i > idx && nums[i] == nums[i - 1]) continue;
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    backtrack(nums, 0, path, res);
    return res;
}

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const res = [],
    path = [];

  function backtrack(idx) {
    res.push([...path]);
    for (let i = idx; i < nums.length; i++) {
      if (i > idx && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return res;
}