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

Part 6 of 16 · ~3 min

Recursion & Backtracking

Two pieces, always: something small enough to answer directly with no further calls, and everything else, which leans on a smaller version of itself already being correct. The planner needs exactly this once prerequisite chains get too deep to count by eye — how many courses stand between a student and one they want to take?

function prereqChainDepth(course) {
  if (!course.prereq) return 0;                       // nothing required first — chain ends here
  return 1 + prereqChainDepth(course.prereq);          // trust the shorter chain is already counted
}

Practicing "trust the recursion" as a habit means resisting the urge to mentally unwind the whole call chain. Take it as given that prereqChainDepth(course.prereq) already returns the right number for the shorter chain, and just check whether adding 1 combines it correctly for the current course. Every recursive function in this piece — tree walks, topological sort, dynamic programming — follows that same shape: decide what the function promises, trust the promise on the smaller call, spend your actual thinking on how to combine the result.

Backtracking, choice by choice

Backtracking layers one rule on top of ordinary recursion: after fully exploring where a choice leads, undo it before moving to the next option. A student has four electives left on a shortlist and 7 credits of room. Which combinations fit?

function electiveCombinations(candidates, creditBudget) {
  const results = [];

  function backtrack(start, chosen, creditsUsed) {
    results.push([...chosen]);                    // every path found so far is a valid answer
    for (let i = start; i < candidates.length; i++) {
      const next = candidates[i];
      if (creditsUsed + next.credits > creditBudget) continue;  // this branch can't fit — skip it
      chosen.push(next);                           // choose
      backtrack(i + 1, chosen, creditsUsed + next.credits);     // explore
      chosen.pop();                                 // un-choose
    }
  }

  backtrack(0, [], 0);
  return results;
}

Calling this "recursion with undo" is fair: the whole decision tree gets walked depth-first with a single chosen array that's mutated in place rather than copied at every level, which is cheap — but the cheapness only stays correct if every choice gets reversed on the way back up before its sibling choice is tried. Leaving out the pop() is the bug almost everyone writes at least once, and it hides well, because nothing looks broken at the moment a result gets recorded. The damage only shows up later, once further recursion keeps changing that same array — by the time you inspect the results, every one of them has quietly become a photo of wherever chosen ended up, not wherever it was when that result was pushed. Copying with [...chosen] instead of pushing chosen itself is the one-line fix, and it's why that line looks the way it does.

A number worth attaching to "exponential" instead of leaving it vague: four candidates means 2⁴ = 16 possible subsets before any pruning, and copying each recorded path costs up to another O(n) — so the raw enumeration runs O(n · 2ⁿ). The creditsUsed + next.credits > creditBudget check is the one line doing the real work: every branch it cuts off is an entire subtree of recursive calls that simply never happens — the gap between checking sixteen combinations and checking a fraction of that.

Recursion on Code Lab has problems built for exactly this.