🗓️ Day 25: Permutations – DFS on All Orders

🧠 Concept Deep Dive

Permutations are all possible orderings of elements. If you’re arranging n items in every possible order, you’re doing permutations. Unlike subsets or combinations, order matters here.

To generate all permutations, we often use backtracking with DFS, building each possible path while marking used elements.

Classic problems:

Permutations (LeetCode 46)
Permutations II (with duplicates)
Next Permutation

These build foundational DFS skills.

🎯 Visual Intuition (ASCII Diagram)

nums = [1, 2, 3]

        []
      /  |  \
    [1] [2] [3]
     |    |    |
 [1,2] [2,1] [3,1] ... etc

Each level explores unused options → leads to full permutation paths.

🛠️ Key Patterns

🧩 Pattern: DFS with "used" array

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const used = Array(nums.length).fill(false);

  function backtrack(path: number[]) {
    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);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return res;
}

📘 Example

Input: nums = [1, 2, 3]

Output:

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

🧪 Homework

Write a function to generate all permutations of a list of distinct numbers.

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

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

🧠 Big-O Cheat Sheet

Time Complexity: O(n!) – All permutations
Space Complexity: O(n!) – For storing results + call stack

🔮 Up Next

▶️ Day 26: Backtracking with Constraints – N-Queens, Sudoku