Backtracking: Choose, Explore, and Restore in JavaScript

Recognize the Pattern

The output asks for combinations, arrangements, placements, or paths under constraints.
Choices depend on the partial candidate, so one global visited set would erase valid alternatives.
The unavoidable number of valid outputs can be exponential; pruning improves practical work but does not erase output cost.

Core Invariant

Each call returns with the working path exactly as it was on entry. Increasing indices enumerate each distinct-input subset once.

Important Boundary

Output snapshots must not alias the mutable path. Visited state for a candidate path must be restored before exploring siblings.

Increasing start indices avoid emitting both [1,2] and [2,1] as separate subsets.

Decide whether order and reuse matter

Input duplicates need an explicit policy. For unique subsets, sort first and skip equal candidates at the same recursion depth; do not globally forbid selecting two equal values that occupy different input positions. Positive-candidate sum pruning stops working if zero or negative candidates can repeat indefinitely.

Output	Next choices	State rule
Subsets of distinct items	Only indices at or after start.	Recurse with index + 1.
Permutations	Any unused item.	Mark used, explore, unmark.
Reusable positive candidates	Current candidate or later.	Recurse with the same index when reuse is allowed.
Word-search path	Adjacent matching unused cell.	Used belongs to the current path, not all searches.
N-Queens	Columns safe in the next row.	Track columns and both diagonal families.

Snapshot outputs; restore working state

Template Assumptions

An array of distinct values; result order follows depth-first increasing-index traversal.
Emits the empty subset and copies each output. Recursive depth is bounded by input length and the runtime stack limit.

JavaScript Template

function subsets(nums) {
  const result = [], path = [];
  function search(start) {
    result.push([...path]);
    for (let index = start; index < nums.length; index++) {
      path.push(nums[index]);
      search(index + 1);
      path.pop();
    }
  }
  search(0);
  return result;
}

Emit a copy of path: this node of the search tree is a valid subset, including the empty subset.
Try each remaining index, append its value, and recurse beyond that index.
Pop before the next sibling branch. The path on return is exactly the path on entry.

Follow the entire search for [1,2]

Action	Working path	Emitted
search(0)	[]	[]
choose 1; search(1)	[1]	[1]
after 1: choose 2; search(2)	[1,2]	[1,2]
undo 2; undo 1	[]	none
choose 2; search(2)	[2]	[2]
undo 2; return	[]	four independent outputs

Step-by-Step: Subsets: choose, copy, and undo

Step 1 / 7

Working path: []
Copied outputs: [[]]

Emit the empty subset

search(0) starts with []. Copy that path into the output; an empty subset is valid too.

Make pruning a proof, not a guess

For N-Queens, row-by-row placement removes row conflicts structurally. Column, row - column, and row + column checks remove only attacked placements.
For Word Search, a visited cell is unavailable only along the current candidate path. Undo its mark before trying another starting cell or branch.
A cheap frequency precheck may reject a word whose letters exceed board multiplicities. It cannot prove that adjacency permits the word.
Finding one valid result may allow early return. Enumeration must explore every remaining valid branch, and restoration must still happen before returning if shared state will be reused.

Include the size of the output

Distinct-input subsets produce 2^N results and N times 2^(N-1) total stored elements: O(N 2^N) time and output space. Working path plus recursive stack is O(N).
Permutations produce N! arrangements; copying each N-element result costs O(N N!) overall, even with efficient used-state checks.
Recursion depth and branching factor are separate. N-Queens can prune heavily, but its worst-case search is not linear. JavaScript has finite call-stack depth.

Mistakes and Counterexamples

Store the mutable path itself in the result.

Counterexample: Pushing path without copying makes all outputs reference the same array, which later pops can leave empty.

Correction: Store [...path] or an equivalent snapshot before changing the working candidate again.

Use one permanent visited set for all candidate paths.

Counterexample: Trying one word-search path through a cell may fail; another starting point can still need that cell for its valid route.

Correction: Unmark the cell when leaving the branch, or use a path-local visited representation.

Recurse without consuming or bounding a reusable choice.

Counterexample: A reusable zero candidate never reduces remaining target, so a recurse-on-same-index sum search can loop forever.

Correction: Require strictly positive reusable candidates or introduce a finite-use bound with a different termination proof.

Last-Minute Recap

Specify order, duplicates, and reuse.
Entry state must equal return state after a branch.
Copy outputs but reuse and restore working state.
Pruning must preserve every feasible answer; include output complexity.

Explain It in an Interview

Does order matter, and can an item be reused?
What makes a pruning condition safe for every possible completion?
How much time and memory are forced by the output size itself?

Ready to Apply This Pattern?

Before coding, explain why this pattern fits and what must stay true at each step. Start with an easier problem, then test that reasoning on a harder variation.

Ordered from Easy to Hard. Premium access requirements still apply.

Difficulty8 problems