Permutations II

Medium Recursion & Backtracking Permutations Original on LeetCode

Reported atOlaMakeMyTrip

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Generate all, deduplicate with a setO(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.

  1. Backtrack as in Permutations; add each full path to a HashSet.
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.

  1. Sort nums.
  2. Skip i if used[i], or if i > 0 && nums[i] == nums[i - 1] && !used[i - 1].
  3. Otherwise mark, add, recurse, remove, unmark.
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, Verbal Arithmetic Puzzle.

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).