Common Backtracking Problems: Permutations, Combinations & N-Queens

The backtracking template — choose, explore, un-choose — is most easily learned by applying it to the classics. This page walks through three canonical problems: permutations (all orderings), combinations (choose k of n), and N-Queens (a constraint puzzle). Each reuses the same skeleton; only the choices, the validity check, and the “complete” condition change.

Permutations

A permutation is an ordering of all elements. [1, 2, 3] has 3! = 6 permutations. The choice at each step is “which unused element goes next?” We mark elements used on the way down and un-mark them on the way back up.

void permute(std::vector<int>& nums, std::vector<bool>& used,
             std::vector<int>& current,
             std::vector<std::vector<int>>& result) {
    if (current.size() == nums.size()) {
        result.push_back(current);          // a full ordering
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;              // skip already-placed elements
        used[i] = true;  current.push_back(nums[i]); // CHOOSE
        permute(nums, used, current, result);         // EXPLORE
        used[i] = false; current.pop_back();          // UN-CHOOSE
    }
}

void permute(int[] nums, boolean[] used, List<Integer> current,
             List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current)); // a full ordering
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;              // skip already-placed elements
        used[i] = true;  current.add(nums[i]); // CHOOSE
        permute(nums, used, current, result);  // EXPLORE
        used[i] = false; current.remove(current.size() - 1); // UN-CHOOSE
    }
}

function permute(nums, used, current, result) {
  if (current.length === nums.length) {
    result.push([...current]);            // a full ordering
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;                // skip already-placed elements
    used[i] = true;  current.push(nums[i]); // CHOOSE
    permute(nums, used, current, result);   // EXPLORE
    used[i] = false; current.pop();         // UN-CHOOSE
  }
}

def permute(nums, used, current, result):
    if len(current) == len(nums):
        result.append(current[:])         # a full ordering
        return
    for i in range(len(nums)):
        if used[i]:
            continue                      # skip already-placed elements
        used[i] = True;  current.append(nums[i])  # CHOOSE
        permute(nums, used, current, result)      # EXPLORE
        used[i] = False; current.pop()            # UN-CHOOSE

Complexity: O(n · n!) — there are n! permutations and copying each costs O(n).

Combinations

A combination chooses k elements where order doesn’t matter: from {1,2,3,4} choosing 2 gives {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}. To avoid duplicates like {2,1}, we only ever pick elements after the last one chosen, tracked by a start index.

void combine(int n, int k, int start, std::vector<int>& current,
             std::vector<std::vector<int>>& result) {
    if ((int)current.size() == k) {
        result.push_back(current);
        return;
    }
    for (int i = start; i <= n; i++) {
        current.push_back(i);                 // CHOOSE i
        combine(n, k, i + 1, current, result); // EXPLORE only larger values
        current.pop_back();                   // UN-CHOOSE
    }
}

void combine(int n, int k, int start, List<Integer> current,
             List<List<Integer>> result) {
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = start; i <= n; i++) {
        current.add(i);                        // CHOOSE i
        combine(n, k, i + 1, current, result); // EXPLORE only larger values
        current.remove(current.size() - 1);    // UN-CHOOSE
    }
}

function combine(n, k, start, current, result) {
  if (current.length === k) {
    result.push([...current]);
    return;
  }
  for (let i = start; i <= n; i++) {
    current.push(i);                        // CHOOSE i
    combine(n, k, i + 1, current, result);  // EXPLORE only larger values
    current.pop();                          // UN-CHOOSE
  }
}

def combine(n, k, start, current, result):
    if len(current) == k:
        result.append(current[:])
        return
    for i in range(start, n + 1):
        current.append(i)                   # CHOOSE i
        combine(n, k, i + 1, current, result)  # EXPLORE only larger values
        current.pop()                       # UN-CHOOSE

Tip: The start index is the difference between combinations and permutations. Permutations revisit every unused element each step; combinations only move forward, which is exactly what removes order from the answer.

N-Queens

Place N queens on an N×N board so none attack each other (no shared row, column, or diagonal). We place one queen per row and try each column, pruning any column or diagonal already under attack. Here we count the number of valid arrangements.

The pruning trick: a queen at (row, col) occupies column col, ”↘” diagonal row - col, and ”↙” diagonal row + col. We track those three with sets.

int solve(int n, int row,
          std::set<int>& cols, std::set<int>& diag1, std::set<int>& diag2) {
    if (row == n) return 1;             // placed a queen in every row
    int count = 0;
    for (int col = 0; col < n; col++) {
        if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col))
            continue;                   // prune: square is attacked
        cols.insert(col); diag1.insert(row - col); diag2.insert(row + col); // CHOOSE
        count += solve(n, row + 1, cols, diag1, diag2);                     // EXPLORE
        cols.erase(col); diag1.erase(row - col); diag2.erase(row + col);    // UN-CHOOSE
    }
    return count;
}

int solve(int n, int row,
          Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
    if (row == n) return 1;             // placed a queen in every row
    int count = 0;
    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col))
            continue;                   // prune: square is attacked
        cols.add(col); diag1.add(row - col); diag2.add(row + col); // CHOOSE
        count += solve(n, row + 1, cols, diag1, diag2);            // EXPLORE
        cols.remove(col); diag1.remove(row - col); diag2.remove(row + col); // UN-CHOOSE
    }
    return count;
}

function solve(n, row, cols, diag1, diag2) {
  if (row === n) return 1;             // placed a queen in every row
  let count = 0;
  for (let col = 0; col < n; col++) {
    if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col))
      continue;                        // prune: square is attacked
    cols.add(col); diag1.add(row - col); diag2.add(row + col); // CHOOSE
    count += solve(n, row + 1, cols, diag1, diag2);            // EXPLORE
    cols.delete(col); diag1.delete(row - col); diag2.delete(row + col); // UN-CHOOSE
  }
  return count;
}

def solve(n, row, cols, diag1, diag2):
    if row == n:
        return 1                        # placed a queen in every row
    count = 0
    for col in range(n):
        if col in cols or (row - col) in diag1 or (row + col) in diag2:
            continue                    # prune: square is attacked
        cols.add(col); diag1.add(row - col); diag2.add(row + col)  # CHOOSE
        count += solve(n, row + 1, cols, diag1, diag2)            # EXPLORE
        cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)  # UN-CHOOSE
    return count

Call it with solve(n, 0, {}, {}, {}). For n = 4 it returns 2; for n = 8, 92.

Going deeper: The diagonal trick (row - col, row + col are constant along each diagonal) turns an O(n) attack check into O(1). This kind of clever state encoding is what makes constraint backtracking practical. N-Queens is O(n!)-ish without pruning; the diagonal/column sets cut the explored tree dramatically.

Practice these on the recursion & backtracking exercises, or see the related backtracking pattern write-up.