9.子集

9.1题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

• 示例一：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

• 示例二：

输入：nums = [0]
输出：[[],[0]]

9.2解法：回溯

9.2.1回溯思路

（1）函数返回值以及参数

private void backing(int startIndex,int[] nums)

（2）终止条件

• 每次递归遍历都要把当前子集加进res中

• 当startIndex大于数组长度，则结束递归

res.add(new ArrayList(paths));
if(startIndex>=nums.length-1){return;
}

（3）遍历过程

for(int i=startIndex;i<nums.length;i++){paths.add(nums[i]);backing(i+1,nums);//回溯paths.remove(nums.length-1);
}

9.2.2代码实现

	List<List<Integer>> res=new ArrayList<>();List<Integer> paths=new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backing(0,nums);return res;}private void backing(int startIndex,int[] nums){res.add(new ArrayList(paths));if(startIndex>nums.length-1){return;}for(int i=startIndex;i<nums.length;i++){paths.add(nums[i]);backing(i+1,nums);//回溯  paths.remove(paths.size()-1);}}

10.子集 ||

10.1题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

• 示例一：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

• 示例二：

输入：nums = [0]
输出：[[],[0]]

10.2解法：回溯

10.2.1回溯思路

• 先将数组排序，这样重复元素肯定相邻
• 同一树层，不可以使用同一元素；同一树枝，可以使用同一元素；
• isUsed[i]：为true，则代表同一树枝用到了元素nums[i]，isUsed[i+1]还可以用

10.2.2代码实现

	List<List<Integer>> res=new ArrayList<>();List<Integer> paths=new ArrayList<>();boolean[] isUsed;public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);isUsed=new boolean[nums.length];Arrays.fill(isUsed,false);backing(0,nums);return res;}private void backing(int startIndex,int[] nums){res.add(new ArrayList(paths));if(startIndex>nums.length-1){return;}for(int i=startIndex;i<nums.length;i++){if(i!=0 && nums[i]==nums[i-1] && isUsed[i-1]==false){//该元素在同一树层已经用过了continue;}{paths.add(nums[i]);isUsed[i]=true;backing(i+1,nums);//回溯  paths.remove(paths.size()-1);isUsed[i]=false;}}}