# Recursion & Backtracking — Part 2: Interview Problems

Six problems built on the same choose → explore → un-choose template, from power sets to N-Queens.

## 1. Subsets (LeetCode 78)

**🟠 Medium.** Return all possible subsets (the power set) of distinct integers `nums`.

```text
nums = [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

**Approach.** Backtracking where every node of the decision tree is a valid subset: record the path on entry, then try adding each later element. (Alternative: start from `[[]]` and, for each number, add it to every existing subset.)

**Complexity.** O(n · 2ⁿ) time and output space.

```typescript
function subsets(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number): void => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  };
  backtrack(0);
  return res;
}
```

```python
def subsets(nums):
    res, path = [], []

    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res
```

## 2. Permutations (LeetCode 46)

**🟠 Medium.** Return all permutations of distinct integers `nums`.

```text
nums = [1,2,3] → 6 permutations
```

**Approach.** At each depth choose any number not yet used (track a `used` array), recurse, then un-mark it. A path of length n is a complete permutation.

**Complexity.** O(n · n!) time.

```typescript
function permute(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [], used = new Array(nums.length).fill(false);
  const backtrack = (): void => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      backtrack();
      path.pop(); used[i] = false;
    }
  };
  backtrack();
  return res;
}
```

```python
def permute(nums):
    res, path, used = [], [], [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res
```

## 3. Combination Sum (LeetCode 39)

**🟠 Medium.** Return all unique combinations of `candidates` (distinct, each usable unlimited times) that sum to `target`.

```text
candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]
```

**Approach.** Sort candidates. Backtrack with a start index (so combinations aren't repeated in a different order) and the remaining target; reuse the same index to allow repetition; `break` as soon as a candidate exceeds what's left.

**Complexity.** Exponential in the worst case; pruning keeps it practical.

```typescript
function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number, remaining: number): void => {
    if (remaining === 0) { res.push([...path]); return; }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break;
      path.push(sorted[i]);
      backtrack(i, remaining - sorted[i]);
      path.pop();
    }
  };
  backtrack(0, target);
  return res;
}
```

```python
def combination_sum(candidates, target):
    candidates = sorted(candidates)
    res, path = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break                       # sorted → nothing later fits either
            path.append(c)
            backtrack(i, remaining - c)     # i, not i + 1: reuse allowed
            path.pop()

    backtrack(0, target)
    return res
```

## 4. Generate Parentheses (LeetCode 22)

**🟠 Medium.** Generate all well-formed strings of `n` pairs of parentheses.

```text
n = 3 → ["((()))","(()())","(())()","()(())","()()()"]
```

**Approach.** Build the string left to right. You may add `(` while fewer than n are open, and `)` while closes < opens. These two rules prune every invalid prefix, so every leaf is valid.

**Complexity.** O(4ⁿ / √n) results (the Catalan number), each O(n) to build.

```typescript
function generateParenthesis(n: number): string[] {
  const res: string[] = [];
  const backtrack = (path: string, opened: number, closed: number): void => {
    if (path.length === 2 * n) { res.push(path); return; }
    if (opened < n) backtrack(path + "(", opened + 1, closed);
    if (closed < opened) backtrack(path + ")", opened, closed + 1);
  };
  backtrack("", 0, 0);
  return res;
}
```

```python
def generate_parenthesis(n):
    res = []

    def backtrack(path, opened, closed):
        if len(path) == 2 * n:
            res.append(path)
            return
        if opened < n:
            backtrack(path + "(", opened + 1, closed)
        if closed < opened:
            backtrack(path + ")", opened, closed + 1)

    backtrack("", 0, 0)
    return res
```

## 5. Word Search (LeetCode 79)

**🟠 Medium.** Return `true` if `word` can be traced through horizontally/vertically adjacent cells of `board`, using each cell at most once.

```text
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED" → true
```

**Approach.** DFS from every cell matching `word[0]`. Mark the cell as visited (temporarily overwrite it), try the four neighbours for the next character, then restore it on the way back: classic backtracking on a grid.

**Complexity.** O(R · C · 3ᴸ) time for word length L (3 directions after the first step), O(L) stack.

```typescript
function exist(board: string[][], word: string): boolean {
  const R = board.length, C = board[0].length;
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = "#";
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (dfs(r, c, 0)) return true;
  return false;
}
```

```python
def exist(board, word):
    R, C = len(board), len(board[0])

    def dfs(r, c, k):
        if k == len(word):
            return True
        if r < 0 or c < 0 or r >= R or c >= C or board[r][c] != word[k]:
            return False
        saved, board[r][c] = board[r][c], "#"        # mark visited
        found = any(dfs(r + dr, c + dc, k + 1) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = saved                          # restore
        return found

    return any(dfs(r, c, 0) for r in range(R) for c in range(C))
```

## 6. N-Queens (LeetCode 51)

**🔴 Hard.** Return the number of ways to place `n` queens on an n×n board so that none attack each other. (LeetCode 51 returns the boards; LeetCode 52 returns the count. The search is identical.)

```text
n = 4 → 2   (n = 8 → 92)
```

**Approach.** Place one queen per row. A column `c` in row `r` is safe if the column, the `r − c` diagonal and the `r + c` anti-diagonal are all free; keep three sets for O(1) checks. Recurse to the next row; undo on return.

**Complexity.** O(n!) time in the worst case, O(n) space.

```typescript
function totalNQueens(n: number): number {
  const cols = new Set<number>(), diag = new Set<number>(), anti = new Set<number>();
  const place = (r: number): number => {
    if (r === n) return 1;
    let count = 0;
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;
      cols.add(c); diag.add(r - c); anti.add(r + c);
      count += place(r + 1);
      cols.delete(c); diag.delete(r - c); anti.delete(r + c);
    }
    return count;
  };
  return place(0);
}
```

```python
def total_n_queens(n):
    cols, diag, anti = set(), set(), set()

    def place(r):
        if r == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c)
            count += place(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
        return count

    return place(0)
```