问题描述
https://leetcode.com/problems/subsets-ii/
解决思路
同78题，需要加入判断重复。
代码
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
//corner case
if(nums.length == 0 || nums == null) return res;
helper(nums, res, new ArrayList<>(), 0);
return res;
}
public void helper(int[] nums, List<List<Integer>> res, List<Integer> list, int start){
res.add(new ArrayList<>(list));
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i - 1]) continue;
list.add(nums[i]);
helper(nums, res, list, i + 1);
list.remove(list.size() - 1);
}
}
}
复杂度分析
- 时间复杂度：O(2^n)
- 空间复杂度：O(1)
