Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解法：
同样是排列问题，这道题去掉了一个限制条件，即可以有重复的元素。考虑例子{1,2,2}，在某次结果得到1，2，2后，在选择第二个元素时，由于2已经被选过，所以第三个2不用放在第二个位置上了，此时的条件为第三个二与第二个二相等，而第二个二还没有被选中，所以，为了避免重复，有限制条件即：
nums[i] == nums[i - 1] && used[i - 1] == 0
注意，这仅仅适用于num中的数是排好序的情况。具体实现代码如下：
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
|
class {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums.length == 0) {
return result;
}
int[] used = new int[nums.length];
List<Integer> tmp = new ArrayList<>();
Arrays.sort(nums);
dfs(nums, used, tmp);
return result;
}
void dfs(int[] nums, int[] used, List<Integer> tmp) {
if (tmp.size() == nums.length) {
result.add(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)) {
continue;
}
tmp.add(nums[i]);
used[i] = 1;
dfs(nums, used, tmp);
used[i] = 0;
tmp.remove(tmp.size() - 1);
}
}
}
|
近期评论