[LeetCode] 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Thought process:
If the collection contains duplicate, I cannot only use the original method I used in "46. Permutations", because it will produce duplicate permutations. For example, if the collection is [0, 1, 1], the result will contain two [0, 1, 1]s.
The idea is to maintain a rule about which one of the duplicate numbers can appear in the permutations. To do this, I can sort the array and make sure that only the number with a smaller index can appear in a duplicate permutation.
For example, as I add numbers to the permutation list, if I found that I'm adding the second 1 while the first 1 is not in the list, that means the first 1 has already been used to make the exact same permutation. So I continue to the next iteration.

Solution:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        List<Integer> permutation = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        permuteUnique(nums, permutation, visited, permutations);
        
        return permutations;
    }
    
    private void permuteUnique(int[] nums, List<Integer> permutation, boolean[] visited, List<List<Integer>> permutations) {
        if (permutation.size() == nums.length) {
            permutations.add(new ArrayList<>(permutation));
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            
            visited[i] = true;
            permutation.add(nums[i]);
            permuteUnique(nums, permutation, visited, permutations);
            permutation.remove(permutation.size() - 1);
            visited[i] = false;
        }
    }
}

Time complexity: O(n! * n).

Comments

  1. Popular Solution Leetcode 46/47
    I found that solution is very popular and helpful: https://youtu.be/UvSPsz0jTQ4

    ReplyDelete

Post a Comment

Popular posts from this blog

[LeetCode] 631. Design Excel Sum Formula

[LeetCode] 269. Alien Dictionary

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee