【算法刷题 | 回溯思想 06】4.17（子集、子集||）

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;

            }
        }
    }