05 August 2008
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]
]
跟第46题相比较，这道题多了一个条件就是有重复数字，题目要求是unique的组合，多了一个步骤就是在结果中去重（使用HashSet），总体解法是类似的。
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
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
dfs(nums, results, new ArrayList<>(), new HashSet<>());// 用一个Set或一维boolean数组来记录元素是否被用过
return results;
}
private void dfs(int[] nums, List<List<Integer>> results, List<Integer> oneResult, Set<Integer> visited) {
if (visited.size() == nums.length) {
results.add(new ArrayList<>(oneResult));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited.contains(i) || (i > 0 && nums[i] == nums[i - 1] && !visited.contains(i - 1))) {
continue;
}
visited.add(i);
oneResult.add(nums[i]);
dfs(nums, results, oneResult, visited);
visited.remove(i);
oneResult.remove(oneResult.size() - 1);
}
}
}