Backtracking Pattern — Subsets, Permutations and N-Queens Template

Backtracking is DFS over a tree of decisions that does not exist in memory — you build a partial answer, extend it, and undo the extension when the branch is exhausted. Every "generate all…" question is this template, and the difference between candidates is almost never the recursion; it is the pruning and the duplicate handling.

The template

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])      # COPY — path keeps mutating
        return

    for choice in choices:
        if not is_valid(choice, path):
            continue                 # prune

        path.append(choice)          # choose
        backtrack(path, next_choices(choice))
        path.pop()                   # un-choose

void backtrack(List<Integer> path, List<Integer> choices) {
    if (isComplete(path)) {
        results.add(new ArrayList<>(path));   // COPY — path keeps mutating
        return;
    }

    for (int choice : choices) {
        if (!isValid(choice, path)) continue;  // prune

        path.add(choice);                      // choose
        backtrack(path, nextChoices(choice));
        path.remove(path.size() - 1);          // un-choose
    }
}

void backtrack(vector<int>& path, const vector<int>& choices) {
    if (isComplete(path)) {
        results.push_back(path);      // COPY — path keeps mutating
        return;
    }

    for (int choice : choices) {
        if (!isValid(choice, path)) continue;   // prune

        path.push_back(choice);                 // choose
        backtrack(path, nextChoices(choice));
        path.pop_back();                        // un-choose
    }
}

function backtrack(path, choices) {
  if (isComplete(path)) {
    results.push([...path]);        // COPY — path keeps mutating
    return;
  }

  for (const choice of choices) {
    if (!isValid(choice, path)) continue;   // prune

    path.push(choice);                      // choose
    backtrack(path, nextChoices(choice));
    path.pop();                             // un-choose
  }
}

Three things to internalise:

`path[:]`, not `path`. Appending the live list stores a reference that is empty by

the time recursion unwinds. This is the single most common backtracking bug.

Every `append` has a matching `pop`. If a branch can return early, the pop must

still happen — keep them adjacent around the recursive call.

Pruning is the whole performance story. The search space is exponential; cutting a

branch at depth 2 removes everything beneath it.

Subsets: include or exclude

def subsets(nums):
    out, path = [], []

    def go(start):
        out.append(path[:])              # every node is an answer, not just leaves
        for i in range(start, len(nums)):
            path.append(nums[i])
            go(i + 1)                    # i + 1: never reuse an element
            path.pop()

    go(0)
    return out

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    go(nums, 0, new ArrayList<>(), out);
    return out;
}

private void go(int[] nums, int start, List<Integer> path,
                List<List<Integer>> out) {
    out.add(new ArrayList<>(path));   // every node is an answer, not just leaves
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        go(nums, i + 1, path, out);   // i + 1: never reuse an element
        path.remove(path.size() - 1);
    }
}

void go(const vector<int>& nums, int start, vector<int>& path,
        vector<vector<int>>& out) {
    out.push_back(path);          // every node is an answer, not just leaves
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        go(nums, i + 1, path, out);   // i + 1: never reuse an element
        path.pop_back();
    }
}

vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> path;
    go(nums, 0, path, out);
    return out;
}

function subsets(nums) {
  const out = [], path = [];

  const go = (start) => {
    out.push([...path]);          // every node is an answer, not just leaves
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      go(i + 1);                  // i + 1: never reuse an element
      path.pop();
    }
  };

  go(0);
  return out;
}

The start index is what stops [1,2] and [2,1] both appearing — subsets are unordered, so each element is only ever considered after the ones before it.

Permutations: order matters

Now every unused element is a candidate at every position, so start is replaced by a used-marker:

def permute(nums):
    out, path = [], []
    used = [False] * len(nums)

    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            go()
            path.pop()
            used[i] = False

    go()
    return out

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    go(nums, new boolean[nums.length], new ArrayList<>(), out);
    return out;
}

private void go(int[] nums, boolean[] used, List<Integer> path,
                List<List<Integer>> out) {
    if (path.size() == nums.length) {
        out.add(new ArrayList<>(path));
        return;
    }
    // Order matters here, so every unused element is a candidate at every
    // position — a used[] flag replaces the start index from Subsets.
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        go(nums, used, path, out);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

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

vector<vector<int>> permute(const vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    go(nums, used, path, out);
    return out;
}

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

  const go = () => {
    if (path.length === nums.length) {
      out.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      go();
      path.pop();
      used[i] = false;
    }
  };

  go();
  return out;
}

The three index rules

Almost every combinatorial question is one of these, and picking the wrong one silently produces duplicates or misses answers:

Recurse with	Effect	Example
`go(i + 1)`	each element used at most once	Subsets, Combinations
`go(i)`	elements may repeat	Combination Sum
`used[]` flags, loop from 0	order matters	Permutations

Skipping duplicates

With repeated values in the input, sort first and skip a candidate equal to its predecessor at the same depth:

nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue                     # same value already tried at this level

Arrays.sort(nums);
for (int i = start; i < nums.length; i++) {
    // i > start, NOT i > 0: a duplicate deeper in the path is legitimate,
    // two identical branches at the same level are not.
    if (i > start && nums[i] == nums[i - 1]) continue;
    // …choose, recurse, un-choose
}

sort(nums.begin(), nums.end());
for (int i = start; i < (int)nums.size(); i++) {
    // i > start, NOT i > 0: a duplicate deeper in the path is legitimate,
    // two identical branches at the same level are not.
    if (i > start && nums[i] == nums[i - 1]) continue;
    // …choose, recurse, un-choose
}

nums.sort((a, b) => a - b);
for (let i = start; i < nums.length; i++) {
  // i > start, NOT i > 0: a duplicate deeper in the path is legitimate,
  // two identical branches at the same level are not.
  if (i > start && nums[i] === nums[i - 1]) continue;
  // …choose, recurse, un-choose
}

i > start is doing the real work: it allows a duplicate deeper in the path ([1,1] is a legitimate subset of [1,1,2]) while blocking two branches at the same level that would generate identical subtrees.

N-Queens: pruning with the right state

The brute force is 8⁸. What makes N-Queens tractable is checking conflicts in O(1) by tracking three sets instead of scanning the board:

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    board, out = [], []

    def go(row):
        if row == n:
            out.append(board[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue
            cols.add(col); diag.add(row - col); anti.add(row + col)
            board.append(col)
            go(row + 1)
            board.pop()
            cols.remove(col); diag.remove(row - col); anti.remove(row + col)

    go(0)
    return out

List<List<Integer>> solveNQueens(int n) {
    List<List<Integer>> out = new ArrayList<>();
    // row - col is constant along a ↘ diagonal, row + col along a ↙ one,
    // so three sets give O(1) conflict checks instead of scanning the board.
    Set<Integer> cols = new HashSet<>(), diag = new HashSet<>(), anti = new HashSet<>();
    go(n, 0, cols, diag, anti, new ArrayList<>(), out);
    return out;
}

private void go(int n, int row, Set<Integer> cols, Set<Integer> diag,
                Set<Integer> anti, List<Integer> board, List<List<Integer>> out) {
    if (row == n) {
        out.add(new ArrayList<>(board));
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag.contains(row - col)
                || anti.contains(row + col)) continue;

        cols.add(col); diag.add(row - col); anti.add(row + col);
        board.add(col);
        go(n, row + 1, cols, diag, anti, board, out);
        board.remove(board.size() - 1);
        cols.remove(col); diag.remove(row - col); anti.remove(row + col);
    }
}

void go(int n, int row, vector<bool>& cols, vector<bool>& diag,
        vector<bool>& anti, vector<int>& board, vector<vector<int>>& out) {
    if (row == n) { out.push_back(board); return; }

    for (int col = 0; col < n; col++) {
        // row - col + n keeps the ↘ index non-negative
        if (cols[col] || diag[row - col + n] || anti[row + col]) continue;

        cols[col] = diag[row - col + n] = anti[row + col] = true;
        board.push_back(col);
        go(n, row + 1, cols, diag, anti, board, out);
        board.pop_back();
        cols[col] = diag[row - col + n] = anti[row + col] = false;
    }
}

vector<vector<int>> solveNQueens(int n) {
    vector<vector<int>> out;
    vector<int> board;
    vector<bool> cols(n, false), diag(2 * n, false), anti(2 * n, false);
    go(n, 0, cols, diag, anti, board, out);
    return out;
}

/* row - col is constant along a ↘ diagonal, row + col along a ↙ one. */
static void go(int n, int row, bool* cols, bool* diag, bool* anti,
               int* board, int (*out)[16], int* count) {
    if (row == n) {
        for (int i = 0; i < n; i++) out[*count][i] = board[i];
        (*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;
        board[row] = col;
        go(n, row + 1, cols, diag, anti, board, out, count);
        cols[col] = diag[row - col + n] = anti[row + col] = false;
    }
}

function solveNQueens(n) {
  const cols = new Set(), diag = new Set(), anti = new Set();
  const board = [], out = [];

  const go = (row) => {
    if (row === n) { out.push([...board]); return; }

    for (let col = 0; col < n; col++) {
      // row - col is constant along a ↘ diagonal, row + col along a ↙ one
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;

      cols.add(col); diag.add(row - col); anti.add(row + col);
      board.push(col);
      go(row + 1);
      board.pop();
      cols.delete(col); diag.delete(row - col); anti.delete(row + col);
    }
  };

  go(0);
  return out;
}

row - col is constant along a ↘ diagonal and row + col along a ↙ one. Placing one queen per row is itself a pruning decision — it removes every arrangement with two queens in a row without ever generating them.

Complexity

Exponential by nature, and you are expected to state which one: subsets O(2ⁿ × n), permutations O(n! × n), combination sum roughly O(2^target), N-Queens O(n!) before pruning. The trailing × n is the cost of copying each answer. Space is O(depth) for the stack plus the output.

Mistakes that cost the round

Appending `path` instead of `path[:]`. Every stored answer ends up empty.
Forgetting to un-choose, so state leaks into sibling branches.
Wrong index rule — go(i) where go(i + 1) was needed produces infinite or

duplicated results.

Deduplicating at the end instead of pruning during. It works and it is slow, and it

is the answer that draws follow-ups.

Skipping with `i > 0` instead of `i > start`, which wrongly kills legitimate

repeats deeper in the path.

What to drill

Subsets — the base template.
Permutations — the used[] variant.
Combination Sum — reuse allowed, prune on the running sum.
Letter Combinations of a Phone Number — a mapped choice set.
Palindrome Partitioning — validity check before recursing.
N-Queens — O(1) conflict checks.
Sudoku Solver — the same, with constraint propagation.

All on the 22 DSA Patterns sheet.

Frequently asked

What is the backtracking template?

Choose, recurse, un-choose. Append a candidate to the current path, recurse on the remaining choices, then pop it before trying the next candidate. Record a copy of the path when it is complete — a copy, because the path list keeps mutating as the recursion unwinds.

How do I avoid duplicate results in backtracking?

Sort the input, then inside the loop skip any candidate where i > start and nums[i] == nums[i-1]. That blocks two identical branches at the same depth while still allowing a repeated value deeper in the same path, which is usually a legitimate answer.

What is the difference between backtracking and DFS?

Backtracking is DFS over an implicit tree of decisions, with an explicit undo step. Plain DFS marks nodes visited permanently because it is exploring a fixed structure; backtracking un-marks on the way out because a choice blocked for one path must be available to another.

Backtracking