Why must backtracking record a copy of the path?

The same path list is reused and modified throughout the search. Appending the list itself stores a reference that keeps changing (and is empty at the end); a copy freezes the answer.

How do subsets and permutations differ in the backtracking template?

Subsets pass a start index so each element is considered once and order doesn't matter, and every path is recorded. Permutations loop over all elements each time, skip ones already used (a used array), and record only full-length paths.

Backtracking: Try, Recurse, Undo — DSA Patterns Made Simple

The problem

Subsets: list every subset of [1, 2, 3] (there are 8, including the empty one). Permutations: list every ordering (there are 6). Loops can't do this for any input size, because the number of nested loops would depend on the input.

How to spot it

"All subsets / permutations / combinations / ways to…"
"Generate every valid…" (parentheses, phone keypad letters, word search paths)
Puzzles with constraints: N-Queens, Sudoku
The output itself is exponential, so an exponential algorithm is expected

The idea

Picture a choose-your-own-adventure book. At each page you make a choice and keep reading. When you reach an ending, you note it, then flip back to the last choice and take the other option. That flipping back is "backtracking".

In code: keep a path (the choices so far). At each step:

If the path is a complete answer, record a copy.
For each available choice: choose (append to path), explore (recurse), un-choose (pop from path).

Add a pruning check before recursing to skip choices that can't lead to a valid answer. That's what makes Sudoku solvers fast.

The template

def backtrack(start, path):
    if is_complete(path):
        results.append(path[:])          # record a COPY
        return
    for i in range(start, len(choices)):
        if not allowed(choices[i], path):
            continue                     # prune
        path.append(choices[i])          # choose
        backtrack(i + 1, path)           # explore
        path.pop()                       # un-choose

function backtrack(start, path) {
  if (isComplete(path)) {
    results.push([...path]);             // record a COPY
    return;
  }
  for (let i = start; i < choices.length; i++) {
    if (!allowed(choices[i], path)) continue;   // prune
    path.push(choices[i]);               // choose
    backtrack(i + 1, path);              // explore
    path.pop();                          // un-choose
  }
}

Worked example

Subsets (every path is an answer), permutations (track which items are used), and combination sum (prune once the total is too big).

Subsets, permutations and combination sumTry it yourself

def subsets(nums):
    results = []

    def backtrack(start, path):
        results.append(path[:])               # every path is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return results


def permutations(nums):
    results, used = [], [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return results


def combination_sum(candidates, target):
    results = []
    candidates = sorted(candidates)

    def backtrack(start, path, total):
        if total == target:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            if total + candidates[i] > target:
                break                          # sorted, so every later choice is too big too
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])   # i, not i + 1: numbers can repeat
            path.pop()

    backtrack(0, [], 0)
    return results


print("subsets:", subsets([1, 2, 3]))
print("permutations:", permutations([1, 2, 3]))
print("sum to 7:", combination_sum([2, 3, 6, 7], 7))

def subsets(nums):
    results = []

def backtrack(start, path):
        results.append(path[:])               # every path is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

backtrack(0, [])
    return results

def permutations(nums):
    results, used = [], [False] * len(nums)

def backtrack(path):
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

backtrack([])
    return results

def combination_sum(candidates, target):
    results = []
    candidates = sorted(candidates)

def backtrack(start, path, total):
        if total == target:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            if total + candidates[i] > target:
                break                          # sorted, so every later choice is too big too
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])   # i, not i + 1: numbers can repeat
            path.pop()

backtrack(0, [], 0)
    return results

print("subsets:", subsets([1, 2, 3]))
print("permutations:", permutations([1, 2, 3]))
print("sum to 7:", combination_sum([2, 3, 6, 7], 7))

Output

subsets: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sum to 7: [[2, 2, 3], [7]]

Subsets, permutations and combination sumTry it yourself

function subsets(nums) {
  const results = [];
  const backtrack = (start, path) => {
    results.push([...path]);                 // every path is a subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  };
  backtrack(0, []);
  return results;
}

function permutations(nums) {
  const results = [], used = new Array(nums.length).fill(false);
  const backtrack = (path) => {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  };
  backtrack([]);
  return results;
}

function combinationSum(candidates, target) {
  const results = [];
  const sorted = [...candidates].sort((a, b) => a - b);
  const backtrack = (start, path, total) => {
    if (total === target) {
      results.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (total + sorted[i] > target) break;   // sorted, so every later choice is too big too
      path.push(sorted[i]);
      backtrack(i, path, total + sorted[i]);   // i, not i + 1: numbers can repeat
      path.pop();
    }
  };
  backtrack(0, [], 0);
  return results;
}

const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
console.log("subsets:", show(subsets([1, 2, 3])));
console.log("permutations:", show(permutations([1, 2, 3])));
console.log("sum to 7:", show(combinationSum([2, 3, 6, 7], 7)));

const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
console.log("subsets:", show(subsets([1, 2, 3])));
console.log("permutations:", show(permutations([1, 2, 3])));
console.log("sum to 7:", show(combinationSum([2, 3, 6, 7], 7)));

Output

subsets: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sum to 7: [[2, 2, 3], [7]]

Common mistakes

Recording path instead of a copy. Every stored answer would point to the same list, which ends up empty.
Forgetting to undo. Without path.pop() (and used[i] = False), choices leak into other branches.
i vs i + 1. Pass i + 1 when each item can be used once, i when it can be reused.
Duplicates in the input. Sort, then skip nums[i] == nums[i-1] at the same level to avoid repeated answers.

Practice

Subsets (medium)
Permutations (medium)

Key points

Choose, explore, un-choose. Record a copy when an answer is complete.
start index → combinations/subsets; used array → permutations.
Prune early to skip hopeless branches.
Exponential by nature: 2ⁿ subsets, n! permutations.