Permutations II

NeetCode: Permutations II · LeetCode: 47. Permutations II · Difficulty: Medium

Given a collection of numbers nums that might contain duplicates, return all possible unique permutations in any order.

Example

Text

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

HashSet iteration order is unspecified, so the programs sort the result before printing, and the output is deterministic.

Brute force: generate all n! orderings, dedupe with a set

Generate every ordering as if all elements were distinct, and insert each into a HashSet<List<Integer>> so repeats collapse. List implements equals and hashCode by content, so two lists with the same values count as one entry (an int[] would not, because arrays compare by identity). LeetCode's Java signature returns List<List<Integer>>.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

        private void generate(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]);
                generate(nums, used, path, seen);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.permuteUnique(new int[] {1, 1, 2})));
        System.out.println(sorted(s.permuteUnique(new int[] {1, 2, 3})));
        System.out.println(sorted(s.permuteUnique(new int[] {2, 2, 2})));
    }
}

Output

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[2, 2, 2]]

The search makes n! leaf visits and hashes O(n)-long lists even when the number of unique permutations is much smaller. Time: O(n * n!). Space: O(n * n!) for the set in the worst case.

Optimal: sort, then skip equal siblings

Sort nums so equal values sit next to each other. Build the permutation position by position with a used array. The duplicate rule: at a given depth, if nums[i] == nums[i - 1] and the previous copy nums[i - 1] is not currently used, skip nums[i].

Why it works: the rule forces equal values to be taken in left-to-right order. If nums[i - 1] is unused when nums[i] is about to be placed, placing nums[i] here would produce the same sequence as placing nums[i - 1] here, since the two are indistinguishable, and the loop already explored that. Each distinct permutation is therefore generated exactly once.

Arrays.sort(int[]) sorts the caller's array in place. LeetCode accepts that; a method that must keep its input unchanged would sort a copy.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> out = new ArrayList<>();
            backtrack(nums, new boolean[nums.length], new ArrayList<>(), out);
            return out;
        }

        private void backtrack(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]);
                backtrack(nums, used, path, out);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.permuteUnique(new int[] {1, 1, 2})));
        System.out.println(sorted(s.permuteUnique(new int[] {1, 2, 3})));
        System.out.println(sorted(s.permuteUnique(new int[] {2, 2, 2})));
    }
}

Output

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[2, 2, 2]]

The work is proportional to the number of unique permutations P (each costs O(n) to copy), plus the internal nodes of the tree. Time: O(n * P) where P <= n!. Space: O(n) recursion and used, not counting the output.