Stop 21 · Data Structures & AlgorithmsTopics · 12/17

Backtracking

In short

'Find all combinations', 'all permutations', 'solve the Sudoku'. Backtracking is a brute force with manners: try a choice, go deeper, and undo it if it doesn't work out.

A refinement of recursion that builds a solution incrementally and abandons ('backtracks from') a path as soon as it's known to be invalid — used for permutations, combinations and puzzles.

The jaadu walks back from a dead end in a narrow old city lane.

Think of it like this

Finding a friend's house in old city lanes

You take a turn. Dead end? Walk back to the last turning and try the next lane. You never restart from the station, you just undo your last choice. That's backtracking.

Watch it happen

All subsets of [1, 2, 3]

[ ]

[1]

[1, 2]

[1, 2, 3]

[1, 3]

[2]

[2, 3]

[3]

1/6backtrack(0) saves the empty path [ ] as the first subset.

The big ideas

What you need to know

Choose, explore, un-choose

Add a choice to the current path, recurse, then remove it so the next choice starts clean.

Prune early

If a path already breaks the rules, stop there. That's what makes it faster than blind brute force.

Save a copy

When a path is complete, push [...path], not path, or every answer will be the same array.

It's still exponential

Subsets are O(2ⁿ) and permutations are O(n!). Fine for n around 10 to 20, not for 1,000.

See it in code

Walk through the code

1function subsets(nums) {2  const result = [];3  const path = [];4 5  function backtrack(start) {6    result.push([...path]); // save a copy7    for (let i = start; i < nums.length; i++) {8      path.push(nums[i]);   // choose9      backtrack(i + 1);     // explore10      path.pop();           // un-choose11    }12  }13  backtrack(0);14  return result;15}

1/4Every path is a valid subset, so save a copy right away.

There are 2ⁿ subsets and copying each costs up to n, so time is O(n · 2ⁿ). The recursion depth and path are O(n), not counting the output.

Save yourself the pain

Common mistakes

Oops

Pushing path itself into result and getting a list of empty arrays.

Do this instead

path keeps changing. Push a copy with [...path] at the moment it's complete.

Oops

Forgetting the pop after the recursive call.

Do this instead

Every push before recursing needs a matching pop after it.

Your mission

Backtracking basics

~45 min

Quick check

How many subsets does a set of 4 distinct items have, including the empty set?

Go deeper

1Solve classic backtracking problems: subsets, permutations, N-Queens.
2Draw the decision tree for a small backtracking problem by hand first.
3Learn to add pruning (early exit) to avoid exploring clearly invalid branches.