Permutations

Medium Problem 87 of 151 Java and Python

Practice on LeetCode

Problem

Given an array nums of distinct integers, return all possible permutations, 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]]

Constraints

1 ≤ nums.length ≤ 6
All integers are unique.

Explanation

Build a permutation position by position. At each position, any number not already used can go there. Try each one, recurse to fill the next position, then free it again.

Approach 1 · Better

Insert into every position

Time O(n · n!)
Space O(n · n!)

Start with one empty permutation. For each new number, insert it into every position of every permutation built so far.

perms = [[]].
For each number, replace perms with every way of inserting it into each existing permutation.

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> perm : perms) {
                for (int pos = 0; pos <= perm.size(); pos++) {
                    List<Integer> copy = new ArrayList<>(perm);
                    copy.add(pos, num);
                    next.add(copy);
                }
            }
            perms = next;
        }
        return perms;
    }
}

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        perms = [[]]
        for num in nums:
            perms = [p[:pos] + [num] + p[pos:] for p in perms for pos in range(len(p) + 1)]
        return perms

Approach 2 · Optimal

Backtracking with a used array

Time O(n · n!)
Space O(n) besides the output

Fill the path one position at a time with any unused number; undo after each recursive call.

If path has n numbers, record a copy.
Otherwise, for every unused nums[i]: mark it used, push, recurse, pop, unmark.

Java

import java.util.*;

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) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result, path = [], []
        used = [False] * len(nums)

        def backtrack():
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i, num in enumerate(nums):
                if used[i]:
                    continue
                used[i] = True
                path.append(num)
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result

Complexity compared

Approach	Time	Space
Better Insert into every position	O(n · n!)	O(n · n!)
Optimal Backtracking with a used array	O(n · n!)	O(n) besides the output

Key takeaways

Subsets and combinations use a start index; permutations use a used array, because order matters.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem