【LeetCode-中等题】90. 子集 II

组合+并集问题汇总：

1、子集非去重版本
2、组合非去重版本
3、组合去重版本

题目

本题nums数组存在重复元素，所以本题会涉及一个去重操作：
子集无需去重版本：【LeetCode-中等题】78. 子集
组合去重版： 【LeetCode-中等题】47. 全排列 II

本题最大的不同就在于组合去重版收获结果是在递归结束末尾，而本题去重收获结果是在递归开始的时候，并且去重操作的条件都是一样的，区别就在于for循环 子集是从startIndex开始的，而 组合都是从0开始的

两者的代码对比

方法一：递归加回溯（去重版）

class Solution {
// 递归加回溯List<List<Integer>> res = new ArrayList<>();//最终结果集public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);//事先对数组进行排序List<Integer>  zres = new ArrayList<>();int startIndex = 0 ;int[] usered = new int[nums.length];//标记数组  0代表未使用   1 代表使用过了dfsback(nums,zres,startIndex,usered);return res;}public void  dfsback(int[] nums, List<Integer> zres,int startIndex,int[] usered){res.add(new ArrayList<>(zres));//收货结果if(startIndex >= nums.length) return ;for(int i = startIndex ; i<nums.length;i++){if(usered[i] == 1) continue;if(i > 0 &&nums[i-1] == nums[i] && usered[i-1] == 0) continue;//去重操作else{zres.add(nums[i]);usered[i] = 1;dfsback(nums,zres,i+1,usered);//下一层递归zres.remove(zres.size()-1);//回溯过程usered[i] = 0;}}}
}