46. Permutations

Understanding Permutations in JavaScript (Step by Step)

Permutations are all the possible arrangements of a given set of numbers.
For example, if we have [1, 2, 3], the permutations are:

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

The problem: Given an array of distinct numbers, generate all possible permutations.

---

The Approach

The trick to solving permutations is recursion + backtracking.
Let’s break down the intuition:

1. Pick one element → Fix it at the end of the current permutation.
2. Recurse on the remaining array → Generate permutations for the rest.
3. Backtrack → Put the element back, so other branches can use it.

In our code:

• We remove the first element using nums.shift().
• Recursively call permute(nums) on the smaller array.
• After recursion, we put the removed element (n) at the end of each permutation.
• Then, restore the element (nums.push(n)) so the array goes back to its original state for the next iteration.

This “remove, recurse, restore” cycle is the backtracking part.

---

Walking Through an Example

Take nums = [1, 2, 3].

1. Remove 1, call permute([2, 3]).

• This generates [2,3] and [3,2].

• Add back 1 → [2,3,1], [3,2,1].

  1. Restore 1. Now remove 2, call permute([1, 3]).

• Generates [1,3] and [3,1].

• Add back 2 → [1,3,2], [3,1,2].

  1. Restore 2. Now remove 3, call permute([1, 2]).

• Generates [1,2] and [2,1].

• Add back 3 → [1,2,3], [2,1,3].

Put it all together → 6 permutations ✅.

---

The Code

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    let result = [];

    // Base case: if there's only one element, return it
    if (nums.length === 1) {
        return [[...nums]]; // make a copy
    }

    // Explore each element
    for (let i = 0; i < nums.length; i++) {
        const n = nums.shift(); // remove first element
        const perms = permute(nums); // recurse on remaining

        // Add the removed element to each permutation
        for (const perm of perms) {
            perm.push(n);
            result.push(perm);
        }

        nums.push(n); // restore the element (backtrack)
    }

    return result;
};

---

Complexity Analysis

• Time Complexity:
  Each permutation has n elements, and there are n! permutations.
  → O(n × n!)

• Space Complexity:

  • The recursion stack goes as deep as n.
  • The result array holds n! permutations, each of size n. → O(n × n!) space as well.

---

Key Takeaways

• The algorithm uses recursion + backtracking.
• At each step, we remove one element, generate permutations of the rest, then restore it.
• The result naturally builds up to all n! permutations.

This is a classic recursive pattern that shows up in many backtracking problems like subsets, combinations, and word search puzzles.

---