Start practising

Permutations

Medium Recursion & Backtracking Permutations Original on LeetCode

Permutations is a medium recursion & backtracking problem solved with the permutations pattern. The best approach, optimal (backtracking with a used array), runs in O(n · n!) time and O(n) space. Below are 2 approaches in Java, from insert into every position up.

Problem

Given an array of distinct integers, return all possible orderings (permutations) of them, in any order.

Examples

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, distinct values.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Insert into every positionO(n · n!)O(n · n!)
Optimal (backtracking with a used array)O(n · n!)O(n)

1Insert into every position

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

Build permutations of the first i elements, then insert nums[i] at every possible position of each.

  1. Start with [[]].
  2. For each x, for each partial p, for each position k, insert x at k.
Java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> perms = new ArrayList<>();
        perms.add(new ArrayList<>());
        for (int x : nums) {
            List<List<Integer>> next = new ArrayList<>();
            for (List<Integer> p : perms)
                for (int k = 0; k <= p.size(); k++) {
                    List<Integer> q = new ArrayList<>(p);
                    q.add(k, x);
                    next.add(q);
                }
            perms = next;
        }
        return perms;
    }
}

2Optimal (backtracking with a used array)

TimeO(n · n!)n! permutations, each copied in O(n). This matches the output size.
SpaceO(n)

At each depth, try every element not yet used, mark it, recurse, then unmark. When the path has n elements it is a full permutation.

  1. If path.size() == n, record a copy.
  2. For each i not used: mark, add, recurse, remove, unmark.
Java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        go(nums, new boolean[nums.length], new ArrayList<>(), out);
        return out;
    }

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

Edge cases to test

  • Single element

Hints

Hint 1

Unlike combinations, order matters: at each position, any unused element can go next.

FAQ

What is the best time complexity for Permutations?

Optimal (backtracking with a used array) runs in O(n · n!) time and O(n) extra space. n! permutations, each copied in O(n). This matches the output size.

Which pattern does Permutations use?

It is a recursion & backtracking problem that uses the permutations pattern. Other problems with the same pattern: Permutations - Swap Trick, Permutations II.

Is there a brute force solution for Permutations?

Yes. Insert into every position takes O(n · n!) time and O(n · n!) space. Build permutations of the first i elements, then insert nums[i] at every possible position of each.

Which edge cases should I test for Permutations?

Single element.