Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If nums =
If nums =
[1,2,2]
, a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
Answer:
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<Integer> subres = new ArrayList<Integer>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
int len = nums.length;
if(len==0)return res;
Arrays.sort(nums);
DFS(res, subres, 0, nums);
return res;
}
public void DFS(List<List<Integer>> res, List<Integer> subres, int index, int[] nums){
List<Integer> newsubres = new ArrayList<Integer>(subres);
res.add(newsubres);
if(index >= nums.length){
return;
}
for(int i=index; i<nums.length; ++i){
//Avoid duplicate set!
if(i!=index && nums[i]==nums[i-1]){
continue;
}
subres.add(nums[i]);
DFS(res, subres, i+1, nums);
subres.remove(subres.size()-1);
}
return;
}
}
No comments:
Post a Comment