🗓️ Day 27: Permutations and Combinations with Backtracking

🧠 Concept Deep Dive

Backtracking shines when solving permutation and combination problems, where we explore all possible sequences or groupings of elements.

Permutations: All possible arrangements of items (order matters).
Combinations: All possible groups of items (order doesn't matter).

Backtracking builds the solution recursively, and undoes choices (“backtracks”) when hitting a dead-end or completing a valid result.

🎯 Visual Intuition (ASCII Tree)

Permutations of [1, 2, 3]:

          []
        /  |  \
      1    2   3
     /\    /\  /\
    2 3   1 3 1 2
    | |   | |  | |
   3  2  3  1 2 1

Each level represents a decision for the next element in the sequence.

🛠️ Key Patterns

🔁 Permutations (using visited set)

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const visited = new Set<number>();

  function backtrack() {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (visited.has(i)) continue;
      visited.add(i);
      path.push(nums[i]);

      backtrack();

      path.pop();
      visited.delete(i);
    }
  }

  backtrack();
  return res;
}

🔢 Combinations (with index forward)

function combine(n: number, k: number): number[][] {
  const res: number[][] = [];

  function backtrack(start: number, path: number[]) {
    if (path.length === k) {
      res.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(1, []);
  return res;
}

📘 Example

Input: nums = [1, 2, 3] → Permutations

Output:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: n = 4, k = 2 → Combinations

Output:

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

🧪 Homework

Write a function to generate all permutations of [1,2,3]

function permute(nums: number[]): number[][] {
// your code
}

Write a function to generate all combinations of size k from n:

function combine(n: number, k: number): number[][] {
// your code
}

🧠 Big-O Cheat Sheet

Permutations:
- Time: O(n!)
- Space: O(n) recursion + output
Combinations:
- Time: O(C(n,k))
- Space: O(k) recursion + output

🔮 Up Next

▶️ Day 28: Subsets and Power Set