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], [] ]
Solution 1: back tracking or DFS
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res=new ArrayList<>();
List<Integer> one=new ArrayList<>();
dfs(0,nums,one,res);
return res;
}
private void dfs(int d, int[] nums, List<Integer> one, List<List<Integer>> res) {
if (d==nums.length) res.add(new ArrayList<Integer>(one));
else {
int i=d+1;
while (i<nums.length && nums[i]==nums[d]) i++;
dfs(i,nums,one,res);//select none
one.add(nums[d]);//select 1+
dfs(d+1,nums,one,res);
one.remove(one.size()-1);
}
}
}
没有评论:
发表评论