Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
1
2
3
4
5
6
7
8
| [
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(nums.length == 0) return ans;
Arrays.sort(nums);
backtrace(ans, new ArrayList<Integer>(), nums, 0);
return ans;
}
public void backtrace(List<List<Integer>> ans, ArrayList<Integer> t, int[] nums, int start){
if(!ans.contains(t))
ans.add(new ArrayList<Integer>(t));
for(int i=start; i<nums.length; i++){
t.add(nums[i]);
backtrace(ans, t, nums, i+1);
t.remove(t.size()-1);
}
}
}
|
