[数据结构与算法]78-子集

题目

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

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

示例 1：

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

示例 2：

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

题解一 dfs+回溯

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        dfs(nums,0,new ArrayList<>(),res);
        res.add(new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums,int layer,List<Integer> subRes,List<List<Integer>> res){
        for(int i=layer;i<nums.length;i++){
            subRes.add(nums[i]);
            res.add(new ArrayList<>(subRes));//注意！
            dfs(nums,i+1,subRes,res);//加深一层
            subRes.remove(subRes.size()-1);//移走自己本身暂存的最后一个
        }
    }
}

笔记：

1. dfs格式：参数：数组，开始层数，sub结果（储存当前暂时的结果），result

   public static void dfs()//参数用来表示状态
   {
   if(到达终点状态) {
   …//根据题意添加
   return;
   }
   if(越界或者是不合法状态)
   return;
   if(特殊状态)//剪枝
   return ;
   for(扩展方式) { //在迷宫中则为四个方向的扩展
   if(扩展方式后的状态可行) { //例如在迷宫中，该方向可行
   修改操作;//根据题意来添加
   标记； //在迷宫中标记为已走过
   dfs（）；
   (还原标记)； //状态回溯，将标记移除
   //是否还原标记根据题意
   }
   }
   }

题解二 迭代法 子集枚举

class Solution {
    List<Integer> temp=new ArrayList<Integer>();
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        int n=nums.length;
        for(int mask=0;mask<(1<<n);mask++){
            //先循环（例如n=3）从000-1000（1000不可达）
            temp.clear();//清除去上次残余的temp
            for(int i=0;i<n;i++){
                if((mask&(1<<i))!=0){
                    //只要！=0就代表nums[i]被包含在mask所示的位中了
                    //每次遍历i位
                    //将实际的nums数组和mask掩码进行与运算
                    temp.add(nums[i]);
                }
            }
            res.add(new ArrayList(temp));//attention
        }
        return res;
    }
}

笔记：

1. 发现 0/10/1 序列对应的二进制数正好从 00 到 2^n - 1。我们可以枚举 mask∈[0, 2^n - 1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/10/1 序列在原集合当中取数。当我们枚举完所有 2^n个mask，我们也就能构造出所有的子集。