[LeetCode] 47. Permutations II

Posted on | In

Problem

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

Example:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Explanation

  1. Similar to 46. Permutations, but this time there are duplicated numbers in the input list, and we don’t want the result list have duplicated sublist.

  2. First, we can sort the input list. We still need a temp list for storing the sublist, and a visited array to check whether the element have been visited or not. Inside the helper method, the base case is if the temp list has length equals to the input array, then we add the temp list as sublist into the result list, and return.

  3. To remove duplicated elements, under the for loop, we can check if i > 0 && nums[i] == nums[i-1] && visited[i-1] == false, then we ignore the current nums[i]. From the above example, we want the first 1, second 1, and 2; in this case, when we iterate to the second 1, it satisify i > 0 && nums[i] == nums[i-1], and now visited[i-1] = visited[0] = true. We don’t want the second 1, first 1, and 2; in this case, when we iterate to the second 1, it satisify i > 0 && nums[i] == nums[i-1] and visited[i-1] = visited[0] = false.

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
class Solution {
    void dfs(int[] nums, List<Integer> temp, List<List<Integer>> res, boolean[] visited) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList(temp));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == false) {
                if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) {
                    continue;
                }
                temp.add(nums[i]);
                visited[i] = true;
                dfs(nums, temp, res, visited);
                temp.remove(temp.size()-1);
                visited[i] = false;
            }
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, temp, res, visited);
        return res;
    }
}