LeetCode - Permutations II
Problem description
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]
]
Analysis
It’s another type of backtrack, the main idea is to ensure duplicate items result in same permutation.
The reason we will get duplicate permutation is that we can’t tell which item we used. For example, suppose we have 1, 1, 2. we have the first 1 selected, and then selected the second 1 in our permutation algorithm, we got a 1, 1, 2. But when we do the next loop, we select the second 1 and then the first one, here we got a duplicated permutation. The reason is that we don’t know the second 1 should be skipped if we used the first one.
So we can select the last unused item in a list of item with same value to prevent duplicate permutation.
Here’s the code:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
backtrack(nums, res, new ArrayList<>(), used);
return res;
}
void backtrack(int[] nums, List<List<Integer>> res, List<Integer> list, boolean[] used){
if (list.size() == nums.length){
res.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < nums.length; i++){
if (used[i]){
continue;
}
while(i < nums.length - 1 && nums[i] == nums[i+1] && !used[i+1]){
i++;
}
used[i] = true;
list.add(nums[i]);
backtrack(nums, res, list, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
What to improve
- index out of range check