DSAMonth 1 · Week 4

Day 16: Recursion & Backtracking Fundamentals

Build the muscle memory for the choose → explore → un-choose backtracking template that solves permutations, combinations, and subsets.

Mark this day complete

Study

Concepts

Recursion needs a base case and a shrinking problem

Every recursive function needs (1) a base case that returns without recursing, and (2) a recursive case that calls itself on a strictly smaller version of the problem, guaranteeing it eventually reaches the base case. Each call adds a frame to the Call Stack (Day 1) — this is why recursion has real memory cost and can overflow.

Backtracking = recursion + undo

Backtracking explores a decision tree by choosing an option, recursing deeper as if that choice were final, and then undoing the choice ("un-choose") when returning, so the next sibling option starts from a clean state. The template is always: `if (base case) { record answer; return }` then `for each choice { make choice; recurse; undo choice }`.

This "undo" step is what separates backtracking from plain recursion — it lets you reuse the SAME array/set across the whole exploration instead of allocating a new copy at every branch, which is both faster and what makes the technique feel tricky the first time.

See It

Visualizations

Visualization

Decision tree for subsets of [1, 2]

Each node is a choice: include or exclude the next number.

[ ] start

include 1 → [1]

include 2 → [1,2]

exclude 2 → [1]

exclude 1 → [ ]

include 2 → [2]

exclude 2 → [ ]

Build It

Code Examples

Subsets — the classic backtracking template

function subsets(nums) {
  const result = [];
  const current = [];

  function backtrack(startIndex) {
    result.push([...current]); // every state along the way is a valid subset

    for (let i = startIndex; i < nums.length; i++) {
      current.push(nums[i]);      // choose
      backtrack(i + 1);            // explore
      current.pop();               // un-choose
    }
  }

  backtrack(0);
  return result;
}

console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Permutations — using a "used" set instead of a start index

function permute(nums) {
  const result = [];
  const current = [];
  const used = new Set();

  function backtrack() {
    if (current.length === nums.length) {
      result.push([...current]);
      return; // base case: no more numbers to place
    }
    for (const num of nums) {
      if (used.has(num)) continue;
      used.add(num);
      current.push(num);

      backtrack();

      current.pop();     // undo
      used.delete(num);  // undo
    }
  }

  backtrack();
  return result;
}

console.log(permute([1, 2, 3]).length); // 6 (3!)

Remember

Key Takeaways

Every recursive function needs a base case AND a step that provably shrinks toward it.
Backtracking template: choose → recurse → un-choose — the un-choose step is what most beginners forget.
Push a COPY ([...current]) into your results array — pushing the live array stores a reference that keeps mutating.
startIndex avoids re-using earlier elements for combinations/subsets; a used Set avoids re-using elements for permutations.
Draw the decision tree on paper before coding — it tells you exactly what the base case and loop bounds should be.

Do It

Practice

1Solve "Combination Sum" (numbers can repeat, must sum to target) by adapting the subsets template.
2Solve "Generate Parentheses" (n pairs, must stay valid) by backtracking on open-count and close-count separately.
3Trace permute([1,2,3]) by hand, drawing the full recursion tree, and count how many times backtrack() is called total.