Backtracking: try a choice, then undo it

Build each answer one choice at a time. After each choice, explore everything that can follow it. Then undo the choice and try the next one. If you do this for every choice, you visit every possible answer exactly once.

Think of it like this: walking through a maze with a ball of string. At every fork you pick a corridor and unroll string behind you. When you reach a dead end, or the exit, you wind the string back to the last fork. Then you try a corridor you haven't tried yet. The string is your path, and winding it back is the undo.

How to spot it

Words and constraints in a problem that point to this pattern:

• “Return all possible …”: all subsets, all orderings, every combination that adds up to a target
• Very small limits on the input: “n ≤ 10”, “the board is at most 6 × 6”, “the word has at most 12 letters”
• A rule about reuse: “each number may be used once” or “may be used any number of times”
• “Does a path exist … without using the same cell twice?”. You try a path, and you give the cells back when it fails
• The number of answers grows very fast as the input grows, like 2ⁿ or n!. Both are explained below

Watch it work

The template

// Every way to choose k items from items, keeping their original order.
function chooseK<T>(items: T[], k: number): T[][] {
  const results: T[][] = [];               // every finished answer goes here

  // path: the choices made so far. start: the first index we may still pick.
  function backtrack(path: T[], start: number): void {
    if (path.length === k) {               // base case: the path is a complete answer
      results.push([...path]);             // save a COPY: path keeps changing after this
      return;                              // a full path can't grow any further
    }
    for (let i = start; i < items.length; i++) {
      const left = items.length - i;       // how many items remain, counting items[i]
      if (path.length + left < k) break;   // prune: even taking all of them can't reach k
      path.push(items[i]);                 // 1. choose
      backtrack(path, i + 1);              // 2. explore: later picks come after i, so no repeats
      path.pop();                          // 3. un-choose: undo, ready to try the next i
    }
  }

  backtrack([], 0);                        // start with nothing chosen, from the first item
  return results;
}

chooseK(["a", "b", "c"], 2); // [["a", "b"], ["a", "c"], ["b", "c"]]

Worked example

1. The first idea is to build every string of length 2n made of ( and ), then keep the balanced ones. Each of the 6 positions has 2 options. So for n = 3 that's 2 × 2 × 2 × 2 × 2 × 2 = 64 strings to check, and only 5 survive. For n = 10 it's over a million strings for 16,796 answers.

2. Notice the waste. Half of those 64 strings start with ). A string that starts by closing a bracket that was never opened can't be fixed by anything after it. But the brute force still builds all 32 of them in full before throwing them away. If we build the string one character at a time, we can stop the moment it goes wrong.

3. That's backtracking. The choice at each step is “add (” or “add )”. Two rules prune the bad branches before they start. Rule 1: you may add ( only while fewer than n have been opened. Rule 2: you may add ) only while fewer have been closed than opened. If you obey both rules, every path that reaches length 2n is balanced. So there's nothing left to check at the end.

4. Write it with the template's shape. Count the opened and closed brackets, so the rules are quick to test. Each branch is choose, explore, un-choose. Joining the path makes a new string, so saving it is already a copy.

   function balancedBrackets(n: number): string[] {
     const results: string[] = [];
   
     function backtrack(path: string[], open: number, close: number): void {
       if (path.length === 2 * n) {          // complete: the rules guarantee it's balanced
         results.push(path.join(""));        // join builds a new string: a copy
         return;
       }
       if (open < n) {                       // rule 1: there's still a bracket left to open
         path.push("(");                     // choose
         backtrack(path, open + 1, close);   // explore
         path.pop();                         // un-choose
       }
       if (close < open) {                   // rule 2: something is open that we can close
         path.push(")");
         backtrack(path, open, close + 1);
         path.pop();
       }
     }
   
     backtrack([], 0, 0);
     return results;
   }
   
   balancedBrackets(3); // ["((()))", "(()())", "(())()", "()(())", "()()()"]
   

5. Check it. For n = 3 it returns the 5 strings above. For n = 1 the only path is ( then ), giving ["()"]. For n = 0 the empty path is already complete, so it returns [""], one empty string. No path ever starts with ), because rule 2 needs close < open and both start at 0. Those 32 strings are never built.

Common mistakes

• Saving path instead of [...path]. Every saved answer is then the same array. After the last pop they all show [], so you get [[], [], []].
• Forgetting path.pop() after the recursive call. The path keeps every old choice. So later answers come out too long, like [a, b, c] when you wanted 2 letters, or the base case is never reached.
• Exploring with start or 0 instead of i + 1 when each item can be used once. You get [a, a]. You also get both [a, b] and [b, a], as if they were different answers.
• Marking something as used, like a grid cell or a used[i] flag, and not unmarking it on the way back. Later paths think it's still taken, so valid answers go missing.
• Pruning with break on input that isn't sorted. “This number is too big, so all the rest are too” is only true after sorting. Without sorting, answers disappear and nothing warns you.

Cost

In interviews