Permutations

mediumBacktracking208 stepsJava · Python · C++

Generate every ordering of distinct numbers. Build the permutation position by position; at each position try every number not used yet, mark it used, recurse, then unmark it.

▶ Watch the animated trace

Traced input: nums = [1, 2, 3] → [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Original problem: neetcode.io/problems/permutations

Complexity

BestO(n·n!)

AverageO(n·n!)

WorstO(n·n!)

SpaceO(n)

n! permutations, each copied in O(n).

Key idea

A boolean used[] array tracks which numbers are already in the path.
When the path has n numbers, it's a complete permutation.
Unmark after recursing so later branches can use the number.

Common mistakes

Using path.contains(x) to check usage is O(n) per check.
Forgetting to copy the path when saving it.

Solution

Java

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

void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        dfs(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Python

def permute(nums: List[int]) -> List[List[int]]:
    res, used = [], [False] * len(nums)

    def dfs(path: List[int]) -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            dfs(path)
            path.pop()
            used[i] = False

    dfs([])
    return res

C++

void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        dfs(nums, used, path, res);
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<bool> used(nums.size());
    vector<int> path;
    dfs(nums, used, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single element One permutation.	`nums = [1]`	`[[1]]`
Two elements 2! = 2 orderings.	`nums = [0, 1]`	`[[0, 1], [1, 0]]`