Permutation

Return all permutation of a number

Permutations — Backtracking in JavaScript

Problem

Given an array of distinct integers, return all possible permutations.

Example:

Input:
[1, 2, 3]

Output:
[
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 2, 1],
  [3, 1, 2]
]

The Solution

var permute = function (nums) {
    var result = [];

    function generatePermute(start) {

        // We have filled all positions
        if (start === nums.length - 1) {
            result.push([...nums]);
            return;
        }

        // Try every remaining number at position `start`
        for (let i = start; i < nums.length; i++) {

            // Choose
            [nums[start], nums[i]] = [nums[i], nums[start]];

            // Explore
            generatePermute(start + 1);

            // Undo the choice
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }

    generatePermute(0);

    return result;
};

Main Idea

The most important idea is:

At every position, try every number that is still available.

For example:

[1, 2, 3]

Position 0:
    Try 1
    Try 2
    Try 3

If we choose 1 for position 0:

[1, 2, 3]
    ↓
Position 0 is fixed

[1, ?, ?]

Now we solve the remaining positions:

Position 1:
    Try 2
    Try 3

This gives:

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

Then we go back and try another number for position 0.

What Does start Mean?

start tells us:

Which position are we currently trying to fill?

For example:

[1, 2, 3]
 ↑
 start = 0

We are deciding what should go at index 0.

After choosing something:

generatePermute(start + 1);

we move to the next position:

[1, 2, 3]
    ↑
  start = 1

Now index 0 is already fixed.

So:

start = 0

[?, ?, ?]


start = 1

[1, ?, ?]


start = 2

[1, 2, ?]

Why Do We Swap?

This line:

[nums[start], nums[i]] = [nums[i], nums[start]];

puts the number at i into the position we're currently trying to fill.

Suppose:

nums = [1, 2, 3]

start = 0
i = 1

We want to try 2 at index 0.

Before:

[1, 2, 3]
 ↑  ↑
start i

Swap:

[nums[0], nums[1]] = [nums[1], nums[0]];

After:

[2, 1, 3]
 ↑
start

Now 2 has been chosen for position 0.

Then We Recurse

After making the choice:

generatePermute(start + 1);

We move to the next position.

So:

[2, 1, 3]
    ↑
  start = 1

Now we decide what goes at index 1.

We can choose:

1

or:

3

Giving:

[2, 1, 3]

[2, 3, 1]

Why Do We Swap Back?

This is the most important part of backtracking.

After exploring a choice:

[nums[start], nums[i]] = [nums[i], nums[start]];

we undo the swap.

For example:

Original:

[1, 2, 3]

Choose 2:

[2, 1, 3]

Explore everything starting with 2.

After we're finished:

[2, 1, 3]

Swap back:

[1, 2, 3]

Now we can try choosing 3.

[3, 2, 1]

Backtracking Pattern

The general pattern is:

// Choose
make a change

// Explore
recursive call

// Undo
reverse the change

In this problem:

// Choose
[nums[start], nums[i]] = [nums[i], nums[start]];

// Explore
generatePermute(start + 1);

// Undo
[nums[start], nums[i]] = [nums[i], nums[start]];

Think:

        CHOOSE
           ↓
        EXPLORE
           ↓
         UNDO
           ↓
     Try next choice

This is the essence of backtracking.

Step-by-Step Example

Let's use:

nums = [1, 2, 3]

Step 1

Call:

generatePermute(0)

We need to decide index 0.

The loop is:

for (let i = 0; i < nums.length; i++)

So we try:

i = 0
i = 1
i = 2

Step 2 — Choose 1

i = 0

[1, 2, 3]
 ↑
start

Swap:

[1, 2, 3]

Then:

generatePermute(1)

Step 3 — Choose 2

Now:

[1, 2, 3]
    ↑
  start

Try i = 1.

Swap:

[1, 2, 3]

Then:

generatePermute(2)

Step 4 — Base Case

Now:

start === nums.length - 1

is true:

2 === 3 - 1

So we have a complete permutation.

result.push([...nums]);

We add:

[1, 2, 3]

to the result.

Why [...nums]?

This is important.

We don't do:

result.push(nums);

because nums is continuously modified by swapping.

Instead:

result.push([...nums]);

creates a copy.

For example:

let nums = [1, 2, 3];

let copy = [...nums];

Now:

nums = [1, 2, 3]
copy = [1, 2, 3]

If we later change nums:

nums = [2, 1, 3]
copy = [1, 2, 3]

The saved permutation remains unchanged.

Step 5 — Backtrack

After finding:

[1, 2, 3]

we return from:

generatePermute(2);

Then we undo our previous choice.

The array returns to:

[1, 2, 3]

Now at start = 1, the loop continues.

Step 6 — Choose 3

At:

[1, 2, 3]
    ↑
  start

now:

i = 2

Swap index 1 and 2:

[1, 3, 2]

Then:

generatePermute(2);

Base case is reached.

Add:

[1, 3, 2]

Now:

result = [
    [1, 2, 3],
    [1, 3, 2]
];

Then swap back:

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

Step 7 — Back to Position 0

We've finished every permutation starting with 1.

Now the loop at start = 0 continues:

i = 1

Swap:

[1, 2, 3]
 ↑  ↑
 0  1

becomes:

[2, 1, 3]

Now index 0 is fixed as 2.

Then:

generatePermute(1);

This produces:

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

Then we backtrack again.

Finally Choose 3

At start = 0:

i = 2

Swap:

[1, 2, 3]
       ↑

becomes:

[3, 2, 1]

Then recursively generate the remaining possibilities:

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

Final Result

The recursion eventually produces:

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

Visualizing the Recursion Tree

The easiest way to understand the recursion is as a tree:

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

Reading from top to bottom gives:

1 → 2 → 3 = [1,2,3]
1 → 3 → 2 = [1,3,2]

2 → 1 → 3 = [2,1,3]
2 → 3 → 1 = [2,3,1]

3 → 2 → 1 = [3,2,1]
3 → 1 → 2 = [3,1,2]

Every path from the root to a leaf is one permutation.

What Exactly Happens in the Loop?

This:

for (let i = start; i < nums.length; i++) {
    [nums[start], nums[i]] = [nums[i], nums[start]];

    generatePermute(start + 1);

    [nums[start], nums[i]] = [nums[i], nums[start]];
}

can be understood as:

For the current position:

    Try the number at index start
        ↓
    Explore all permutations

    Undo

    Try the next number
        ↓
    Explore all permutations

    Undo

    Try the next number
        ↓
    Explore all permutations

    Undo

Why Does i Start at start?

Notice:

for (let i = start; i < nums.length; i++)

not:

for (let i = 0; i < nums.length; i++)

Why?

Because everything before start is already fixed.

For example:

[2, 1, 3]
 ↑  ↑  ↑
 |  |  |
 |  |  current position
 |  already fixed
 already fixed

If:

start = 2

we only care about index 2.

We don't want to touch:

index 0
index 1

because those positions have already been chosen.

So:

i = start

means:

"Only consider numbers that haven't already been fixed."

The Base Case

if (start === nums.length - 1) {
    result.push([...nums]);
    return;
}

When start reaches the final index, every previous position has already been chosen.

For:

[1, 2, 3]

when:

start = 2

we have:

index 0 → chosen
index 1 → chosen
index 2 → automatically remaining

Therefore:

[1, 2, 3]

is a complete permutation.

We save it and return.

A Mental Model

Don't think of the code as:

"I'm swapping random elements."

Instead think:

"I'm choosing which number belongs at the current position."

For example:

start = 0

Which number should be at position 0?

    1
    2
    3

Choose 1.

[1, ?, ?]

Then:

start = 1

Which number should be at position 1?

    2
    3

Choose 2.

[1, 2, ?]

The remaining number must be 3.

[1, 2, 3]

Save it.

Then backtrack and try another choice.

The Three Important Operations

Remember these three words:

1. CHOOSE
2. EXPLORE
3. UNDO

In code:

// CHOOSE
[nums[start], nums[i]] = [nums[i], nums[start]];

// EXPLORE
generatePermute(start + 1);

// UNDO
[nums[start], nums[i]] = [nums[i], nums[start]];

This pattern appears in many backtracking problems.

Examples:

• Permutations
• Subsets
• Combination Sum
• N-Queens
• Sudoku
• Word Search
• Generate Parentheses

Complexity

For n numbers, there are:

n!

possible permutations.

For:

[1,2,3]

there are:

3! = 6

For:

[1,2,3,4]

there are:

4! = 24

For:

[1,2,3,4,5]

there are:

5! = 120

So the time complexity is approximately:

O(n × n!)

because there are n! permutations and copying each permutation takes O(n).

The result itself requires:

O(n × n!)

space because we store all permutations.

One-Sentence Summary

The algorithm repeatedly:

Choose a number for the current posi