LeetCode 47. Permutations II

Question

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Source: https://leetcode.com/problems/permutations-ii/

Solution

The following code shows two solutions for this problem. One constructs permutations by swap, the other by append. The idea of swap solution is explained in detail in post LeetCode 46. Permutations.

The key point of de-duplication is to avoid traversing duplicate elements on the same DFS layer. By doing so, we can avoid duplicate permutation prefixes. Because constructing permutations is a recursive process, we guarantee that there is no duplicates in the final result.

The swap solution achieves this by maintaining a set for each layer. For the append solution, we choose to use a character-count map. And on each layer, we traverse its key set rather than entry set so that we avoid duplicate elements.

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

// the depth of dfs equals to the length of the array
// elements before position are regarded as fixed
private void dfs(int[] nums, int position, List<List<Integer>> result) {
    if (position == nums.length - 1) {
        List<Integer> permutation = new ArrayList<>();
        for (int n : nums) {
            permutation.add(n);
        }
        result.add(permutation);
    }

    // to store used elements in this layer
    // if two prefixes are identical, their dfs results must contain duplicates
    Set<Integer> used = new HashSet<>();
    for (int i = position; i < nums.length; i++) {
        if (!used.contains(nums[i])) {
            used.add(nums[i]);
            // backtrace
            swap(nums, position, i);
            dfs(nums, position + 1, result);
            swap(nums, position, i);
        }
    }
}

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> unique = new ArrayList<>();
    dfs(nums, 0, unique);
    return unique;
}

// the depth of dfs equals to the length of the array
// elements before position are regarded as fixed
private void dfs2(int length, LinkedList<Integer> current, Map<Integer, Integer> dict, List<List<Integer>> result) {
    if (current.size() == length) {
        List<Integer> copy = new ArrayList<>(current);
        result.add(copy);
    }

    // traverse its key set instead of entry set to avoid duplicates
    for (Integer e : dict.keySet()) {
        int count = dict.get(e);
        if (count == 0) {
            continue;
        }
        // backtrace
        // do not remove key even if its value is 0, so as not to interfere map traversal
        current.addLast(e);
        dict.put(e, count - 1);

        dfs2(length, current, dict, result);

        current.removeLast();
        dict.put(e, count);
    }
}

public List<List<Integer>> permuteUnique2(int[] nums) {
    List<List<Integer>> unique = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    LinkedList<Integer> permute = new LinkedList<>();
    for (int n : nums) {
        map.put(n, map.getOrDefault(n, 0) + 1);
    }
    dfs2(nums.length, permute, map, unique);
    return unique;
}