90.子集II题目描述给你一个整数数组nums其中可能包含重复元素请你返回该数组所有可能的 子集幂集。解集不能包含重复的子集。返回的解集中子集可以按任意顺序排列。示例 1输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2输入nums [0] 输出[[],[0]]提示1 nums.length 10-10 nums[i] 10代码classSolution{// 存放最终结果ListListIntegerresultnewArrayList();// 当前路径当前子集ListIntegerpathnewLinkedList();/** * 回溯函数 * * param nums 排序后的数组 * param startIndex 本层递归开始的位置 * param used 记录当前路径中哪些元素被使用过 */publicvoidbacktracking(int[]nums,intstartIndex,int[]used){// 每到一个节点都把当前路径加入结果result.add(newLinkedList(path));// 横向遍历同一树层for(intistartIndex;inums.length;i){/** * 树层去重核心 * * nums[i] nums[i - 1] * 说明当前元素和前一个元素相同 * * used[i - 1] 0 * 说明前一个元素已经回溯结束 * 即 * 前一个元素和当前元素处于同一树层 * * 同一层中相同元素只取第一个 */if(istartIndexnums[i-1]nums[i]used[i-1]0){continue;}// 做选择path.add(nums[i]);// 标记当前元素已使用进入树枝used[i]1;// 递归下一层backtracking(nums,i1,used);// 回溯撤销选择used[i]0;// 删除当前路径最后一个元素path.removeLast();}}publicListListIntegersubsetsWithDup(int[]nums){// 必须先排序// 这样相同元素才会相邻才能进行去重Arrays.sort(nums);// used数组// 1 表示当前元素在当前路径中// 0 表示当前元素不在当前路径中int[]usednewint[nums.length];backtracking(nums,0,used);returnresult;}}
90.子集II题目描述给你一个整数数组nums其中可能包含重复元素请你返回该数组所有可能的 子集幂集。解集不能包含重复的子集。返回的解集中子集可以按任意顺序排列。示例 1输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2输入nums [0] 输出[[],[0]]提示1 nums.length 10-10 nums[i] 10代码classSolution{// 存放最终结果ListListIntegerresultnewArrayList();// 当前路径当前子集ListIntegerpathnewLinkedList();/** * 回溯函数 * * param nums 排序后的数组 * param startIndex 本层递归开始的位置 * param used 记录当前路径中哪些元素被使用过 */publicvoidbacktracking(int[]nums,intstartIndex,int[]used){// 每到一个节点都把当前路径加入结果result.add(newLinkedList(path));// 横向遍历同一树层for(intistartIndex;inums.length;i){/** * 树层去重核心 * * nums[i] nums[i - 1] * 说明当前元素和前一个元素相同 * * used[i - 1] 0 * 说明前一个元素已经回溯结束 * 即 * 前一个元素和当前元素处于同一树层 * * 同一层中相同元素只取第一个 */if(istartIndexnums[i-1]nums[i]used[i-1]0){continue;}// 做选择path.add(nums[i]);// 标记当前元素已使用进入树枝used[i]1;// 递归下一层backtracking(nums,i1,used);// 回溯撤销选择used[i]0;// 删除当前路径最后一个元素path.removeLast();}}publicListListIntegersubsetsWithDup(int[]nums){// 必须先排序// 这样相同元素才会相邻才能进行去重Arrays.sort(nums);// used数组// 1 表示当前元素在当前路径中// 0 表示当前元素不在当前路径中int[]usednewint[nums.length];backtracking(nums,0,used);returnresult;}}
