Solution Space Trees

Medium

The tree every backtracking solution walks

Problem

Understand how backtracking explores a tree of partial solutions, pruning branches that cannot lead to a valid answer.

In simple words

Every choice is a branch; you walk down building a solution and back up to try others.

The idea

Every backtracking algorithm is a depth-first walk of a tree whose nodes are partial solutions and whose branches are the choices available next. Backtracking differs from brute force only in that it abandons a branch the moment it cannot lead to a valid answer — that pruning is the entire optimisation.

The trick

Choose, explore, un-choose: the three lines every such function contains.
Prune at the earliest point the constraint can be checked, not at the leaves.
The cost is roughly (branching factor) ^ (depth) minus whatever you prune.

←→stepspaceplay

1/10

Optimal

timeO(n·2ⁿ)spaceO(n)

Branch on each element.

1function dfs(i, path) {2  if (i === n) { out.push([...path]); return; }3  dfs(i + 1, path);          // exclude4  path.push(nums[i]);5  dfs(i + 1, path);          // include6  path.pop();7}

Input

array: [1, 2, 3]

Memory

subset: —

Output

count: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:: subsets of [1,2]
Output:: tree with 4 leaves

Finished the walkthrough? Add it to your streak.