73.Permutations

MediumBacktracking · 3/9

Problem

Given an array nums of distinct integers, return all possible permutations — every ordering of all the elements. The answer may be returned in any order.

Examples

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Explanation: 3 distinct elements have 3! = 6 orderings.

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

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

Constraints

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

💡 Key Insight

Build a permutation one position at a time: the first slot has n choices, the next n - 1, and so on, giving n! leaves. The only thing to track is which elements are already used — a boolean[] used array, or swapping elements into a prefix of the array so the "unused" ones are always the suffix.

Insertion (Iterative)

TimeO(n · n!)SpaceO(n · n!)

Intuition

Every permutation of [1..k] is obtained by taking a permutation of [1..k-1] and inserting element k into one of its k gaps. Start from [[]] and grow.

Algorithm

perms = [[]].
For each num in nums:
- next = [].
- For every p in perms and every position pos in 0..p.size(): copy p, insert num at pos, add to next.
- perms = next.
Return perms.

Visualization

start      : [[]]
insert 1   : [[1]]
insert 2   : [[2,1], [1,2]]
insert 3   : [[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]]

Code

java

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> perms = new ArrayList<>();
        perms.add(new ArrayList<>());
        for (int num : nums) {
            List<List<Integer>> next = new ArrayList<>();
            for (List<Integer> p : perms) {
                // insert num into every gap of p (including both ends)
                for (int pos = 0; pos <= p.size(); pos++) {
                    List<Integer> copy = new ArrayList<>(p);
                    copy.add(pos, num);
                    next.add(copy);
                }
            }
            perms = next;
        }
        return perms;
    }
}

Complexity

Time: O(n · n!) — the last round builds n! lists of length n; earlier rounds are smaller.
Space: O(n · n!) — the intermediate lists of the previous round plus the output.

Backtracking with a Used Array

TimeO(n · n!)SpaceO(n)

Intuition

Fill the permutation left to right. At each step try every element not yet used, mark it, recurse, then unmark it (backtrack). When path has n elements, it is complete.

Algorithm

dfs(): if path.size() == n, record a copy.
For each i with !used[i]: set used[i] = true, push nums[i], dfs(), pop, used[i] = false.

Visualization

flowchart TD
    R["path=[]"] -->|"1"| A["[1]"]
    R -->|"2"| B["[2]"]
    R -->|"3"| C["[3]"]
    A -->|"2"| A1["[1,2] → [1,2,3]"]
    A -->|"3"| A2["[1,3] → [1,3,2]"]
    B -->|"1"| B1["[2,1] → [2,1,3]"]
    B -->|"3"| B2["[2,3] → [2,3,1]"]
    C -->|"1"| C1["[3,1] → [3,1,2]"]
    C -->|"2"| C2["[3,2] → [3,2,1]"]

Code

java

import java.util.*;

class Solution {
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();

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

    private void dfs(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // already placed in this permutation
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used);
            path.remove(path.size() - 1); // undo the choice
            used[i] = false;
        }
    }
}

Complexity

Time: O(n · n!) — n! leaves, each copied in O(n); internal nodes scan n indices.
Space: O(n) — used, path and recursion depth (output excluded).

In-Place SwappingOptimal

TimeO(n · n!)SpaceO(n)

Intuition

Keep the array itself as the permutation being built. Positions 0..start-1 are fixed; positions start..n-1 are the unused pool. To choose the element for slot start, swap each candidate nums[i] (i >= start) into slot start, recurse on start + 1, then swap back. No used array and no path list are needed.

Algorithm

permute(start): if start == n, record the array as a list.
For i from start to n - 1:
- swap(start, i); permute(start + 1); swap(start, i).

Visualization

nums = [1,2,3]

start=0: swap(0,0) [1,2,3]
           start=1: swap(1,1) [1,2,3] -> record
                    swap(1,2) [1,3,2] -> record, swap back -> [1,2,3]
         swap(0,1) [2,1,3]
           start=1: [2,1,3] record, [2,3,1] record
         swap back -> [1,2,3]
         swap(0,2) [3,2,1]
           start=1: [3,2,1] record, [3,1,2] record

Code

java

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            result.add(perm);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);           // place nums[i] at position start
            backtrack(nums, start + 1, result);
            swap(nums, start, i);           // restore for the next choice
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

Complexity

Time: O(n · n!) — same number of leaves, each copied in O(n).
Space: O(n) — recursion depth only.

Complexity Comparison

Approach	Time	Space (extra)
Insertion	O(n · n!)	O(n · n!)
Backtracking + used[]	O(n · n!)	O(n)
In-place Swapping	O(n · n!)	O(n)

Common Pitfalls

Forgetting to reset used[i] = false after the recursive call — later branches never see that element again.
Forgetting the second swap — the array is left scrambled and later permutations repeat or go missing.
Adding path instead of a copy of it.
Starting the inner loop at start with a used array (that is the combinations pattern) — permutations need every unused index, from 0.