Be the Computer

You have the array 123. Your job: generate every possible ordering using only swaps.

You decide what to swap, when to go deeper, and when to undo. No hints, no labels — just you and the array.

You are the computer
1
2
3
Array is 123. To generate all permutations, you need to try each element in position 0. What is your first move?
1 / 5

Predict the State

Here is the test: can you track the array through the choose and unchoose steps? After each swap or un-swap, predict the resulting array before it is revealed.

The un-swaps are the important ones. If you can predict those correctly, you understand why backtracking works.

Step 1/5
1
2
3
chooseCHOOSE: swap(0, 1)

We start with [1, 2, 3]. To put 2 first, we swap positions 0 and 1.

What does the array look like after this choose?

The Three-Phase Loop

You just saw the skeleton that every backtracking solution shares:

1. Choose — modify the state. Add an element to the path. Swap a value into position. Place a queen on the board. Whatever the problem requires.

2. Explore — recurse into the subproblem. From this point, the algorithm acts as if your choice is permanent. It goes deeper and deeper.

3. Unchoose — undo the modification. Remove the element. Swap the value back. Take the queen off the board. Restore the state to exactly what it was before step 1.

The undo step is not cleanup — it is the defining mechanism. Without it, the second branch starts from the modified state left by the first branch. The mutations accumulate. Every branch after the first produces garbage.

Think of it this way: the choose step writes in pencil, and the unchoose step erases. The next branch gets a clean sheet to write on.

Copy vs Mutate

“Why bother with the undo step at all? Why not just copy the array at each level and recurse with the copy?”

Fair question. Copying works. But how much does it cost? Predict the memory for each array size before you see the answer.

n=3
1
2
3

3! = 6 paths, each copies 3 elements

Permutations of 123: at each recursion level you copy the array. How many total cells are copied across all 3! = 6 paths?

1 of 3

The Base Case Trap

There is a classic bug that every backtracking beginner hits — usually in the first week. It looks correct. It runs without errors. But every result in the output is an empty array.

The code below generates subsets. Run it and see what happens. Then find the buggy line and fix it.

Hint: the bug is in what gets pushed, not when it gets pushed.

1function subsets(nums) {
2 const result = [];
3 const path = [];
4
5 function backtrack(start) {
6 result.push(path); // ← look closely
7 for (let i = start; i < nums.length; i++) {
8 path.push(nums[i]);
9 backtrack(i + 1);
10 path.pop();
11 }
12 }
13 backtrack(0);
14 return result;
15}

When to Stop

Every backtracking solution needs a base case — the point where you stop recursing. But base cases in backtracking serve a different purpose than in normal recursion.

In merge sort, the base case is “array has one element — nothing to sort.” That is a structural base case.

In backtracking, the base case answers a semantic question: “Is this partial solution complete? Is it valid? Should I collect it?” Different problems have very different answers:

  • Subsets: collect at every node (every partial path is a valid subset)
  • Permutations: collect when depth equals n (all elements placed)
  • Combination Sum: collect when the remaining target equals 0

For each problem below, pick the correct base case condition.

Question 1/3
Generate all subsets of n elements
function backtrack(start) {
  if (___) { result.push([...path]); return; }
  ...
}

When do we have a complete subset?

Write the Permutation Code

You have swapped, predicted, and debugged. Now write the actual function.

The permutation template uses the same choose-explore-unchoose skeleton as subsets, but the choose step is a swap (fix an element at position start) and the unchoose step is the reverse swap. Fill in the four critical blanks.

function permute(nums) {
const result = [];
function backtrack(start) {
if () {
;
return;
}
for (let i = start; i < nums.length; i++) {
;// choose
backtrack(start + 1);// explore
;// un-choose
}
}
backtrack(0);
return result;
}

Your Call

Three questions on the Choose-Explore-Unchoose template, the undo step, and base case design.

Question 1/3
The undo step

What makes backtracking different from brute-force recursion?