Permutations

BACKTRACKING · MEDIUM

The problem

Given an array nums of distinct integers, return all possible permutations, in any order.

Solution 1: Brute force — remove-and-recurse (array copy each step)

At each step, pick one element from what’s left, build a NEW array with it removed (via slice + concat), and recurse on that shorter array. This is simple and correct, but rebuilding the “remaining” array costs O(n) at every single step of the recursion.

Brute force: remove an element by copying the rest — O(n) per pick

pick remaining[i]          slice + concat           recurse on new array
(add it to path)      →    (O(n) copy to remove it) →  (repeat until empty)

Cost: O(n) extra work at every single recursion node.

Interactive visualization

Brute force: nums=[1,2] — remove an element via slice+concat at each step

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

This animation traces nums=[1,2] — a small case verified above.

The code

function permuteBrute(nums) {
  const result = [];
  function dfs(remaining, path) {
    if (remaining.length === 0) { result.push(path.slice()); return; }
    for (let i = 0; i < remaining.length; i++) {
      const next = remaining.slice(0, i).concat(remaining.slice(i + 1));
      path.push(remaining[i]);
      dfs(next, path);
      path.pop();
    }
  }
  dfs(nums, []);
  return result;
}

Line by line:

remaining.slice(0, i).concat(remaining.slice(i + 1)) builds an entirely new array missing index i — this is the O(n) cost paid at every node.
The recursion’s base case (remaining.length === 0) is reached exactly when every element has been placed into path.
path.slice() is used when recording, for the same reason it matters in every other backtracking problem in this batch — path is a shared, mutating array.

Complexity

Metric	Value
Time	O(n² × n!)
Space	O(n) recursion depth

Solution 2: Optimal — in-place swap

Instead of building new arrays, swap the chosen element into position k directly inside the original array, recurse, then swap back — O(1) per pick instead of O(n).

Optimal: swap in place — O(1) per pick

swap arr[k], arr[i]        recurse on k+1              swap back
(O(1), no copy)      →  (same array, one position over) →  (restore before next i)

Cost: O(1) extra work per recursion node instead of O(n).

Interactive visualization

Optimal: nums=[1,2] — in-place swap at each step

Press Play or Step to begin.

call stack depth: 0

Step 0 / 0

This animation also traces nums=[1,2] — the same small case verified above.

The code

function permuteOptimal(nums) {
  const result = [];
  const arr = nums.slice();
  function dfs(k) {
    if (k === arr.length) { result.push(arr.slice()); return; }
    for (let i = k; i < arr.length; i++) {
      [arr[k], arr[i]] = [arr[i], arr[k]];
      dfs(k + 1);
      [arr[k], arr[i]] = [arr[i], arr[k]];
    }
  }
  dfs(0);
  return result;
}

Line by line:

[arr[k], arr[i]] = [arr[i], arr[k]] swaps two positions with destructuring assignment — no temp variable needed, no new array allocated.
dfs(k + 1) fixes position k and recurses on everything after it — by the time k === arr.length, every position has been fixed by exactly one swap.
Swapping back ([arr[k], arr[i]] = [arr[i], arr[k]] again) after the recursive call is essential — without it, the array’s order would stay permanently scrambled for the NEXT iteration of the loop.

Complexity

Metric	Value
Time	O(n × n!)
Space	O(n) recursion depth

Complexity comparison

Solution	Time	Extra space per node
Brute force (slice+concat)	O(n² × n!)	O(n) array copy
Optimal (in-place swap)	O(n × n!)	O(1) swap

Unlike Subsets, this IS a genuine asymptotic improvement — the brute-force version pays an extra O(n) at every single recursion node just to remove one element, while the optimal version does that in O(1) with a swap.

Interview corner

Q: How would you extend this to handle duplicate values, like [1,1,2], without duplicate permutations in the output?

Sort the array first.
At each recursion level, track which values have already been used at THIS specific position, and skip a duplicate value if an identical earlier value at this level wasn’t used yet — a specific, well-known duplicate-skipping condition for permutations with repeats.

Q: Why does the optimal solution still need arr.slice() when recording into result, even though it swaps instead of slicing to build the permutation?

arr is still ONE shared, mutating array throughout the whole recursion, exactly like every other backtracking problem in this batch.
The same reference-copy trap applies here too, just triggered by swaps instead of push/pop.

Q: What’s the space complexity of each solution, beyond the O(n · n!) needed just to store the output?

Brute force — O(n) extra per recursion level for the sliced “remaining” array, times O(n) recursion depth, giving O(n²) auxiliary space beyond the output.
Optimal — O(1) extra per recursion level, so only O(n) auxiliary space total, for the recursion depth itself.

Q: Trick question — what does this log?

const nums = [10, 2, 1];
console.log(JSON.stringify(nums.sort()));

Answer: [1,10,2], not [1,2,10].
.sort() with no comparator converts every element to a STRING and compares them lexicographically (character by character).
“10” sorts before “2” because ‘1’ comes before ‘2’ as a character, even though 10 > 2 numerically.
⚠ Trap: The correct fix is nums.sort((a, b) => a - b) — always pass an explicit numeric comparator when sorting numbers in JavaScript, never rely on the default.

Permutations

The problem

Solution 1: Brute force — remove-and-recurse (array copy each step)

Interactive visualization

The code

Complexity

Solution 2: Optimal — in-place swap

Interactive visualization

The code

Complexity

Complexity comparison

Interview corner

Quiz