Backtracking Patterns: The One Template Behind Subsets, Permutations, and N-Queens

The mental model: backtracking is DFS on a decision tree

Every backtracking problem builds a candidate solution one decision at a time. At each step you have a set of choices. You pick one, descend into the smaller problem that remains, and when that branch is fully explored you return to where you were and try the next choice. That return — the undo — is the "back" in backtracking, and it's the step beginners forget.

Picture the recursion as a tree. The root is the empty candidate. Each edge is a choice. Each node is a partial solution, and the leaves are complete candidates. A brute-force solution would generate every leaf blindly. Backtracking walks the same tree but prunes whole branches the instant they can't lead to a valid answer, which is what makes it tractable.

The hardest part to trust is the un-choose step. After a recursive call returns, you must put the state back exactly as it was before the call — pop the element you pushed, unmark the cell you marked, decrement the counter you incremented. If you forget, choices leak across branches and the output is silently wrong. This is the single most common backtracking bug, and it's almost impossible to spot by reading code. You have to watch the path grow and shrink.

The universal template

Almost every backtracking solution you will ever write is this shape. The parts that change between problems are small and predictable: the base case that records or rejects a candidate, the set of choices available at each level, and the optional pruning check that skips invalid branches early.

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

  for (const choice of choices) {
    if (!isValid(path, choice)) continue;  // pruning — skip dead branches

    path.push(choice);              // CHOOSE
    backtrack(path, nextChoices);   // EXPLORE the subproblem
    path.pop();                     // UN-CHOOSE — restore state
  }
}

Pattern 1: Subsets — the include / exclude tree

Subsets is the cleanest backtracking problem because there is no goal to reach — every node is a valid answer. At each index you make a binary decision: include this element in the current subset, or skip it. The start index is what guarantees you never reuse an earlier element, so you generate each subset exactly once.

function subsets(nums) {
  const results = [];

  function backtrack(start, path) {
    results.push([...path]);        // record at EVERY node

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);           // CHOOSE nums[i]
      backtrack(i + 1, path);       // EXPLORE — i+1 prevents reuse
      path.pop();                   // UN-CHOOSE
    }
  }

  backtrack(0, []);
  return results;
}

Pattern 2: Permutations — track what's used

Permutations differ from subsets in one way: order matters and you use every element. So instead of a start index, you need a way to know which elements are already in the current path. A boolean used[] array is the standard tool. The base case fires when the path has used all n elements.

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

  function backtrack(path) {
    if (path.length === nums.length) {   // base case: full permutation
      results.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;             // skip elements already in path

      used[i] = true; path.push(nums[i]);   // CHOOSE
      backtrack(path);                       // EXPLORE
      path.pop(); used[i] = false;           // UN-CHOOSE (both!)
    }
  }

  backtrack([]);
  return results;
}

Pattern 3: Combination Sum — reuse and target pruning

Combination Sum introduces two new wrinkles: elements can be reused, and there is a numeric target to hit. Reuse means you recurse with i instead of i + 1, so the same element can be chosen again. The target is what enables real pruning — once the remaining target goes negative, the whole branch is dead and you stop immediately.

function combinationSum(candidates, target) {
  const results = [];

  function backtrack(start, path, remaining) {
    if (remaining === 0) {            // exact hit — record it
      results.push([...path]);
      return;
    }
    if (remaining < 0) return;        // PRUNE — overshot, dead branch

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);                  // CHOOSE
      backtrack(i, path, remaining - candidates[i]); // i, not i+1 → reuse
      path.pop();                                // UN-CHOOSE
    }
  }

  backtrack(0, [], target);
  return results;
}

Pruning: where backtracking earns its name (N-Queens)

Subsets and permutations explore the full tree because every branch is valid. Constraint problems are different: most branches are dead ends, and the entire skill is cutting them as early as possible. N-Queens is the canonical example. Placing a queen that attacks an existing one can never lead to a valid board, so you reject it before recursing — pruning an exponential subtree in one check.

The implementation detail that separates a clean N-Queens from a slow one is how you check attacks. Tracking three sets — occupied columns, occupied "↘" diagonals (row - col), and occupied "↙" diagonals (row + col) — makes the validity check O(1) instead of scanning the board each time. You add to the three sets on choose and remove from them on un-choose, the same symmetric pattern as every other backtracking problem.

This is why pruning is the heart of the technique. The skeleton is identical to subsets; what makes N-Queens solvable for n = 12 instead of timing out is that isValid kills most of the tree before you ever descend into it. When you optimize a backtracking solution, you are almost always making the pruning check sharper or earlier, never touching the choose/explore/un-choose loop.

Complexity: why backtracking is exponential (and that's expected)

Backtracking problems are exponential by nature, and interviewers know it. The point is not to make them polynomial — it's to state the complexity correctly and prune well. Subsets is O(2^n) because there are 2^n subsets and you copy each one. Permutations is O(n · n!) because there are n! permutations, each of length n. Combination Sum has no simple closed form and is usually bounded by the tree size, O(n^(target/min)).

The strong move in an interview is to say the complexity out loud and explain that pruning changes the constant and the practical runtime, not the worst-case bound. "This is O(2^n) in the worst case because the output itself is exponential, but the validity check prunes most branches, so in practice it finishes far faster." That sentence shows you understand both the theory and why the algorithm is still the right choice.

What interviewers actually look for

In a backtracking interview, writing the recursion correctly is expected. What separates strong candidates is naming the structure before they write a single line. "This is a backtracking problem. My choices at each step are the unused numbers, my base case is a full-length path, and I'll undo each choice after recursing." That framing tells the interviewer you see the tree, not just the syntax.

They also watch for the two bugs that reveal a shallow understanding: forgetting to copy the path on record, and forgetting to restore state on un-choose. Candidates who have only memorized solutions trip on both the moment the problem deviates from the version they practiced. Candidates who understand the template handle any variation, because the variation only changes the base case, the choices, and the pruning — never the loop.

The highest-value habit you can build is articulating the pruning. For constraint problems, say explicitly which branches you cut and why: "I skip any column that's attacked, so I never explore boards that are already invalid." Pruning is where backtracking stops being brute force, and naming it is the clearest signal that you understand what the technique is actually doing.

Frequently asked questions