DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Recursion & Backtracking

Recursion is built from exactly two pieces: a base case that stops the recursion outright, and a recursive case that solves the problem by trusting a smaller version of itself to already be correct.

function factorial(n) {
  if (n <= 1) return 1;               // base case
  return n * factorial(n - 1);        // trust that factorial(n - 1) is already correct
}

"Trust the recursion" is the actual mental move worth practicing: don't try to mentally unwind the entire call chain to convince yourself it works. Assume factorial(n - 1) correctly returns (n-1)!, and then just verify that multiplying it by n is the right way to combine that trusted result into an answer for n. Every recursive algorithm in this piece — tree traversal, DP, backtracking — is built the same way: define what the function promises to return, trust that promise on the smaller call, and only think hard about how to combine that trusted result.

The backtracking template

Backtracking is recursion applied to building something up choice by choice, with one added step: after exploring everything a choice leads to, undo it before trying the next one.

function backtrack(path, choices) {
  if (isCompleteSolution(path)) {
    recordSolution(path);
    return;
  }
  for (const choice of choices) {
    if (!isValid(choice, path)) continue;    // prune invalid branches before ever recursing into them
    path.push(choice);                        // choose
    backtrack(path, remainingChoices(choices, choice));  // explore
    path.pop();                               // un-choose
  }
}

function subsets(nums) {
  const result = [];
  function backtrack(start, path) {
    result.push([...path]);          // every path along the way is itself a valid subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);            // choose
      backtrack(i + 1, path);        // explore
      path.pop();                    // un-choose
    }
  }
  backtrack(0, []);
  return result;
}

That's why backtracking is fairly described as "recursion with undo": it explores the entire decision tree depth-first using one shared, mutated path array rather than allocating a fresh copy at every level, which is far cheaper — but only correct if every choice made on the way down gets undone on the way back up before the next sibling choice is tried. Forgetting the pop() is the single most common backtracking bug, and it manifests in a specifically confusing way: the collected results don't look wrong at the point each one is pushed, but by the time the recursion finishes mutating that same shared array further, every recorded result silently reflects the final state instead of the state at the moment it was recorded — which is exactly why result.push([...path]) copies the array instead of pushing path itself.

Backtracking problems are frequently exponential in the worst case — you're enumerating some or all of a combinatorial space — which makes the isValid pruning check inside the loop the single highest-leverage line in the whole template: every branch it skips is a whole subtree of recursive calls that never happens.

Practice this on Code Lab: Recursion