Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
首先对数组进行排序，这样重复的元素将排列在一起。
接下来对每一个层级进行回溯。
进入每一个层级都根据上一级传递来的列表创建新列表。
然后对层级下的所有元素进行回溯。
剪枝，当遍历节点和上一个节点相等时，则跳过。
回溯，从列表中去掉最后一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
Arrays.sort(nums);
backtrack(ret, new LinkedList<Integer>(), nums, 0);
return ret;
}
private void backtrack(List<List<Integer>> ret, List<Integer> arr, int[] nums, int level){
ret.add(new LinkedList<>(arr));
for(int i = level; i < nums.length; i++){
if(i != level && nums[i] == nums[i-1]) continue;
arr.add(nums[i]);
backtrack(ret, arr, nums, i+1);
arr.remove(arr.size()-1);
}
}
}
|
