6.1 Recursion Fundamentals & Subsets

1. What Are Recursion & Backtracking?

• Recursion is when a function solves a big problem by calling itself on a slightly smaller version of the same problem, stopping as soon as it hits a simple Base Case.
• Backtracking is recursion used to explore a tree of choices: you make a choice (path.append(x)), recurse deeper to see where it leads, and then undo that choice (path.pop()) when you return so you can try the next branch cleanly!

2. Why Do We Need Recursion & How Does the Call Stack Work?

Why Can't We Just Use for Loops?

If someone asks for all 2-element pairs of [1, 2, 3], you can write 2 nested for loops. If they ask for all subsets of an array of length N, you would need N nested loops — which is impossible to write when N is an input variable! In recursion, each recursive call acts as one nested loop level, dynamically stacking N levels deep on the computer's Call Stack.

The 3 Laws of Every Recursive / Backtracking Function

1. Base Case (When to Stop): Check if you've reached the end of the array or found a valid solution. Without a base case, recursion overflows the call stack!
2. Choose & Explore (Recursive Step): Add a candidate to path and call dfs(next_index).
3. Undo / Backtrack: Because path is a single shared list in memory, you must path.pop() right after the recursive call returns, restoring path to how it looked before!

2B. Warm-Up Walkthrough: How the Call Stack Unwinds (factorial(4) & Binary Strings)

Before jumping into Subsets, let's trace how a simple 1-branch recursion (factorial(3)) and a 2-branch recursion (generate binary strings of length 2) execute on the computer's Call Stack:

• Going Down (Pushing Stack Frames): fact(3) pauses and calls fact(2), which pauses and calls fact(1).
• Hitting the Base Case (n == 1): fact(1) returns 1 immediately without making another call.
• Unwinding Back Up (Popping Stack Frames): fact(2) wakes up, computes 2 * 1 = 2, and returns 2 to fact(3), which computes 3 * 2 = 6!

# Warm-Up 1: Simple Recursion (Sum 1..n) -> O(N) time, O(N) call stack space
def sum_to_n(n: int) -> int:
  if n <= 1:          # 1. Base Case
      return n
  return n + sum_to_n(n - 1)  # 2. Smaller Subproblem

# Warm-Up 2: Generate All Binary Strings of Length n ("00", "01", "10", "11")
def binary_strings(n: int) -> list[str]:
  res, path = [], []
  def dfs() -> None:
      if len(path) == n:
          res.append("".join(path))
          return
      for bit in ("0", "1"):
          path.append(bit)  # Choose
          dfs()             # Explore
          path.pop()        # Undo!
  dfs()
  return res

3. Basic Operations & Walkthroughs (All 4 Languages)

# Generate all 2^N Subsets of nums using Pick / Skip Backtracking
def subsets(nums: list[int]) -> list[list[int]]:
  res = []
  path = []

  def backtrack(start: int) -> None:
      # Save a COPY of the current basket at every node in the tree
      res.append(path[:])
      for i in range(start, len(nums)):
          path.append(nums[i])   # 1. Choose nums[i]
          backtrack(i + 1)       # 2. Explore remaining elements
          path.pop()             # 3. Undo choice (Backtrack!)

  backtrack(0)
  return res

4. Core Interview Patterns & Common Traps

Handling Duplicate Numbers in Subsets (Subsets II)

What if the input array contains duplicates, like nums = [1, 2, 2], and the problem asks for unique subsets (so [1, 2] isn't generated twice)?

1. Sort nums first (nums.sort()) so identical numbers sit side-by-side.
2. Inside the for i in range(start, len(nums)) loop, add one line: if i > start and nums[i] == nums[i - 1]: continue Why i > start? Because picking the first 2 at i == start (to form [1, 2, 2]) is completely valid, but picking the second 2 in the exact same loop position after popping the first 2 would start a duplicate branch!

nums.sort()  # Sort first if input has duplicates!
res, path = [], []
def backtrack(start: int) -> None:
  res.append(path[:])  # Always append a SHALLOW COPY of path
  for i in range(start, len(nums)):
      if i > start and nums[i] == nums[i - 1]:
          continue     # Skip duplicate sibling branch
      path.append(nums[i])
      backtrack(i + 1)
      path.pop()

5. Practice On Your Own (Curated Submodule Problems)