Backtracking

How to think about it

At each step, try a choice, recurse, then undo. The call stack is the current path. Prune when the partial solution cannot lead to a valid complete one. Order choices carefully to avoid duplicate outputs.

Template shapes

Shape	Core move	Notes
Subsets	Include or skip each element	Push path copy at every node
Permutations	Swap or used[] mask	Length == n → record
Combinations	Start index i	Avoid reordering duplicates

Complexity baseline

Output-sensitive: often O(n·#solutions). Extra space O(n) recursion depth.

From template to problem

1. Define the state (path, index, remaining target, used mask).
2. Base case: record a complete valid path.
3. Loop choices; push; recurse; pop.
4. Add pruning (sum too large, cell visited, etc.).

/** Backtracking template: subsets (choose / skip via start index). */
export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

/** Backtracking template: subsets (choose / skip via start index). */
export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}