LeetCode #46 — Medium

Permutations

A complete visual walkthrough of the backtracking approach — building a decision tree to generate every arrangement.

The Problem

Problem Statement

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

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Roadmap

The Brute Force Idea
The Core Insight — Backtracking with Used Array
Walkthrough — Decision Tree for [1,2,3]
Edge Cases
Full Annotated Code
Interactive Demo
Complexity Analysis

Step 01

The Brute Force Idea

To generate all permutations, we need to place each element in each possible position. For n elements, the first position has n choices, the second has n-1, and so on.

Counting Permutations

n = 1

1 permutation

n = 3

3! = 6 permutations

n = 6

6! = 720 permutations

We can't avoid generating all n! permutations — that's the output size. But we can generate them efficiently using a systematic exploration strategy.

💡

Backtracking is the standard template for exhaustive enumeration problems. Build a candidate solution incrementally, and "undo" (backtrack) each choice before trying the next one. This avoids creating n! separate arrays upfront.

Step 02

The Core Insight — Backtracking with Used Array

We maintain a path (current partial permutation) and a used boolean array to track which elements are already placed.

The Backtracking Template

1. Base case: path.size() == n

All positions filled — add a copy of path to the result.

2. Choose: try each unused element

For each nums[i] where used[i] == false: mark it used, add to path.

3. Explore: recurse to fill next position

Call backtrack() recursively to continue building the permutation.

4. Unchoose: backtrack

Remove from path, mark used[i] = false. Now try the next element.

⚡

Why copy the path? We add new ArrayList<>(path) because path is mutated during backtracking. Without the copy, all entries in the result would reference the same (eventually empty) list.

Step 03

Walkthrough — Decision Tree for [1,2,3]

Each level of the tree represents choosing which element to place at that position. Leaves are complete permutations.

The Decision Tree

[ ]

choose 1st element

/ | \

[1]

[2]

[3]

choose 2nd element

/ \ / \ / \

[1,2]

[1,3]

[2,1]

[2,3]

[3,1]

[3,2]

choose 3rd (last) element

| | | | | |

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

6 complete permutations (3! = 6)

Backtracking Trace for the [1,2,3] Branch

choose 1 path=[1] used=[T,F,F]

choose 2 path=[1,2] used=[T,T,F]

choose 3 path=[1,2,3] used=[T,T,T] -> COLLECT!

undo 3 path=[1,2] used=[T,T,F]

undo 2 path=[1] used=[T,F,F]

choose 3 path=[1,3] used=[T,F,T]

choose 2 path=[1,3,2] used=[T,T,T] -> COLLECT!

... continues for [2,...] and [3,...] branches

Step 04

Edge Cases

Single element

[1] -> [[1]] — one permutation. The recursion immediately hits the base case.

Two elements

[1,2] -> [[1,2],[2,1]] — 2! = 2 permutations. The simplest case that exercises all parts of the algorithm.

Negative numbers

[-1,0,1] — works exactly the same. The algorithm doesn't depend on element values, only their positions and uniqueness.

All elements are distinct (guaranteed)

The problem guarantees distinct integers. For duplicates, you'd need Permutations II (#47) with sorting and skip logic.

Step 05

Full Annotated Code

class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new boolean[nums.length],
                  new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used,
                           List<Integer> path,
                           List<List<Integer>> result) {

        // Base case: all positions filled
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // copy!
            return;
        }

        // Try each unused element
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;       // skip used

            // Choose
            used[i] = true;
            path.add(nums[i]);

            // Explore
            backtrack(nums, used, path, result);

            // Unchoose (backtrack)
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

func permute(nums []int) [][]int {
    result := [][]int{}
    used := make([]bool, len(nums))

    var backtrack func(path []int)
    backtrack = func(path []int) {

        // Base case: all positions filled
        if len(path) == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path) // copy!
            result = append(result, tmp)
            return
        }

        // Try each unused element
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue // skip used
            }

            // Choose
            used[i] = true
            path = append(path, nums[i])

            // Explore
            backtrack(path)

            // Unchoose (backtrack)
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    backtrack([]int{})
    return result
}

def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []

    def backtrack(path: list[int], used: list[bool]) -> None:

        # Base case: all positions filled
        if len(path) == len(nums):
            result.append(path[:])  # copy!
            return

        # Try each unused element
        for i in range(len(nums)):
            if used[i]:
                continue               # skip used

            # Choose
            used[i] = True
            path.append(nums[i])

            # Explore
            backtrack(path, used)

            # Unchoose (backtrack)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

impl Solution {
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut used = vec![false; nums.len()];
        let mut path = Vec::new();
        backtrack(&nums, &mut used, &mut path, &mut result);
        result
    }
}

fn backtrack(
    nums: &[i32],
    used: &mut Vec<bool>,
    path: &mut Vec<i32>,
    result: &mut Vec<Vec<i32>>,
) {
    // Base case: all positions filled
    if path.len() == nums.len() {
        result.push(path.clone()); // copy!
        return;
    }

    // Try each unused element
    for i in 0..nums.len() {
        if used[i] { continue; } // skip used

        // Choose
        used[i] = true;
        path.push(nums[i]);

        // Explore
        backtrack(nums, used, path, result);

        // Unchoose (backtrack)
        path.pop();
        used[i] = false;
    }
}

function permute(nums: number[]): number[][] {
    const result: number[][] = [];

    function backtrack(path: number[], used: boolean[]): void {

        // Base case: all positions filled
        if (path.length === nums.length) {
            result.push([...path]); // copy!
            return;
        }

        // Try each unused element
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;       // skip used

            // Choose
            used[i] = true;
            path.push(nums[i]);

            // Explore
            backtrack(path, used);

            // Unchoose (backtrack)
            path.pop();
            used[i] = false;
        }
    }

    backtrack([], new Array(nums.length).fill(false));
    return result;
}

Step 06

Interactive Demo

Enter distinct integers and watch the backtracking algorithm build permutations step by step through the decision tree.

Backtracking Visualizer

nums (comma-separated)

Step 07

Complexity Analysis

Time

O(n! × n)

Space

O(n)

We generate all n! permutations. Copying each permutation into the result takes O(n), giving O(n! × n) total time. The recursion stack and used boolean array each use O(n) space (not counting the output itself).

Approach Breakdown

BRUTE FORCE

O(n! × n) time

O(n) space

The recursion tree has n branches at level 1, n-1 at level 2, and so on -- producing n! leaf nodes (complete permutations). Each leaf requires an O(n) copy into the result, giving O(n! × n) total work. The recursion stack and used[] array each use O(n).

OPTIMAL

O(n! × n) time

O(n) space

Backtracking with a boolean used[] array generates exactly n! permutations with no wasted work. The O(n) copy per permutation is unavoidable since every permutation must appear in the output. No algorithm can beat O(n! × n) because that is the output size itself.

🎯

n! is inherent -- every permutation must be generated. The factor of n comes from copying each permutation into the result. No algorithm can do better than O(n! × n) since the output itself has that size. Backtracking achieves this bound with minimal overhead.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Missing undo step on backtrack

Wrong move: Mutable state leaks between branches.

Usually fails on: Later branches inherit selections from earlier branches.

Fix: Always revert state changes immediately after recursive call.