企业官网建设流程全解析

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{// 存放最终结果List<List<Integer>>result=newArrayList<>();// 当前路径（当前子集）List<Integer>path=newLinkedList<>();/** * 回溯函数 * * @param nums 排序后的数组 * @param startIndex 本层递归开始的位置 * @param used 记录当前路径中哪些元素被使用过 */publicvoidbacktracking(int[]nums,intstartIndex,int[]used){// 每到一个节点，都把当前路径加入结果result.add(newLinkedList<>(path));// 横向遍历（同一树层）for(inti=startIndex;i<nums.length;i++){/** * 树层去重（核心） * * nums[i] == nums[i - 1] * 说明当前元素和前一个元素相同 * * used[i - 1] == 0 * 说明前一个元素已经回溯结束 * 即： * 前一个元素和当前元素处于同一树层 * * 同一层中，相同元素只取第一个 */if(i>startIndex&&nums[i-1]==nums[i]&&used[i-1]==0){continue;}// 做选择path.add(nums[i]);// 标记当前元素已使用（进入树枝）used[i]=1;// 递归下一层backtracking(nums,i+1,used);// 回溯：撤销选择used[i]=0;// 删除当前路径最后一个元素path.removeLast();}}publicList<List<Integer>>subsetsWithDup(int[]nums){// 必须先排序// 这样相同元素才会相邻，才能进行去重Arrays.sort(nums);// used数组：// 1 表示当前元素在当前路径中// 0 表示当前元素不在当前路径中int[]used=newint[nums.length];backtracking(nums,0,used);returnresult;}}