How do you list every possible subset of 123? A recursive function that makes one decision at a time: include this element, or skip it?

Tap to step through. Watch the tree grow AND the code panel below it — each tap runs one line of the function. The annotation shows what happened to path.

function subsets(idx, path) {

  if (idx === nums.length) {

    result.push([...path])

    return

  }

  path.push(nums[idx])      // include

  subsets(idx + 1, path)     // explore

  path.pop()                 // un-choose

  subsets(idx + 1, path)     // explore without

}

Now it is your turn. Make those decisions yourself.

Below is a tree and the function that builds it. Tap Include or Exclude — watch which line of code runs and how path changes in the state bar.

At a leaf, result.push([...path]) collects the subset. Then path.pop() fires to undo the last choice, and the tree backtracks to the other branch.

Walk every branch. Collect all 8 subsets.

function subsets(idx, path) {

  if (idx === nums.length) {

    result.push([...path])

    return

  }

  path.push(nums[idx])      // include

  subsets(idx + 1, path)     // explore

  path.pop()                 // un-choose

  subsets(idx + 1, path)     // explore without

}

That function never allocated a tree. No new TreeNode(), no adjacency list, no data structure at all. Yet a tree appeared — each function call became a node, each recursive call became an edge.

This is the key insight behind backtracking: the recursion IS the tree. Every backtracking problem — subsets, permutations, N-Queens, Sudoku — works this way. The algorithm walks an implicit decision tree where:

• Each level represents one choice to make
• Each branch represents one option for that choice
• Each leaf is a complete candidate (which may or may not be valid)

The tree lives only in the call stack. When the function returns, that branch vanishes. The tree is never in memory — it unfolds as the recursion runs.

You built the tree by making choices — include or skip, over and over. But the computer doesn't see a tree. It runs one function at a time.

When it calls a new function, the old one pauses. When the new one finishes, it has to go back. But back to where?

Let's find out what that feels like.

The subset tree was binary — at each level, you chose “include” or “exclude.” Two branches per node, always.

Permutations have a completely different shape. At level 0, you pick from all elements. At level 1, you pick from the remaining ones. At level 2, only one element is left. The branching factor shrinks as you go deeper: 3 ⟶ 2 ⟶ 1.

Build all permutations of [A, B, C] and feel the difference. Notice how the tree narrows instead of staying uniform.

You have now built two very different trees using the exact same template (choose ⟶ recurse ⟶ unchoose). The only thing that changed was the shape — how many branches exist at each level.

This is a powerful idea: if you can describe the tree a problem produces, you can write the backtracking solution. The questions become:

• What does each level decide?
• How many branches does each node have?
• When does a path end (base case)?

Match each problem below to the tree shape its backtracking would produce.

Students often confuse DFS (depth-first search) with backtracking because the code looks nearly identical. Both use recursion. Both go deep before going wide. But they differ in one critical way: what happens to nodes after you visit them.

DFS on a real graph marks nodes permanently. Once a node is colored gray or black, it stays that way forever. You are traversing a structure that already exists.

Backtracking marks nodes temporarily. When you retreat from a branch, you undo the mark — restoring the state so the next branch starts fresh. You are constructing candidates on an imaginary tree.

Watch both run side by side. Step through them together and watch the difference in marking behavior.

You have seen the tree grow, traced the call stack, and compared DFS with backtracking. Now write the actual function.

The code panel has been beside you the whole time — same function, same lines. Fill in the four critical blanks: when to stop, what to collect, how to choose, and how to undo.

Three questions to check whether the decision tree mental model has landed.