Permutations II

Medium Recursion & Backtracking Permutations Original on LeetCode

Permutations II is a medium recursion & backtracking problem solved with the permutations pattern. The best approach, optimal (sort + skip duplicate choices), runs in O(n · n!) time and O(n) space. Below are 2 approaches in Java, from generate all, deduplicate with a set up.

Problem

Given an array that may contain duplicates, return all unique permutations, in any order.

Examples

Example 1

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

Example 2

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

Constraints

1 <= nums.length <= 8; duplicates allowed.

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.

Code

Code appears here once we start writing it.

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.

Approach	Time	Space
Generate all, deduplicate with a set	`O(n · n!)`	`O(n · n!)`
Optimal (sort + skip duplicate choices)	`O(n · n!)`	`O(n)`

1Generate all, deduplicate with a set

TimeO(n · n!)

SpaceO(n · n!)

Generate every permutation with the used-array method and store them in a set.

Backtrack as in Permutations; add each full path to a HashSet.

Java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Set<List<Integer>> seen = new HashSet<>();
        go(nums, new boolean[nums.length], new ArrayList<>(), seen);
        return new ArrayList<>(seen);
    }

    private void go(int[] nums, boolean[] used, List<Integer> path, Set<List<Integer>> seen) {
        if (path.size() == nums.length) { seen.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, seen);
            path.remove(path.size() - 1); used[i] = false;
        }
    }
}

2Optimal (sort + skip duplicate choices)

TimeO(n · n!)

SpaceO(n)

Sort so duplicates are adjacent. Treat equal values as ordered copies: copy i may be placed only after copy i - 1 is already in the path. If nums[i] == nums[i - 1] and !used[i - 1], placing copy i now would produce a permutation you will also produce with copy i - 1, so skip it.

Sort nums.
Skip i if used[i], or if i > 0 && nums[i] == nums[i - 1] && !used[i - 1].
Otherwise mark, add, recurse, remove, unmark.

Java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(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;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) 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

All values equal (one permutation)

Hints

Hint 1

Sort. Among equal values, only use them in left-to-right order: skip nums[i] if it equals nums[i - 1] and nums[i - 1] is not currently used.

FAQ

What is the best time complexity for Permutations II?

Optimal (sort + skip duplicate choices) runs in O(n · n!) time and O(n) extra space.

Which pattern does Permutations II use?

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

Is there a brute force solution for Permutations II?

Yes. Generate all, deduplicate with a set takes O(n · n!) time and O(n · n!) space. Generate every permutation with the used-array method and store them in a set.

Which edge cases should I test for Permutations II?

All values equal (one permutation).