从零学算法78

发布时间:2024年01月18日

78.给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]

  • 如果将该题想象成一棵 n 叉树,进行 dfs,那么其实遍历时走过的每个路径都是子集。比如例子 1
  •   		1
      	2		3
      3
    
  • 为了防止重复组合,所以在构建新的子集时,比如 [1,3] 我们继续构建时,不会往前取数字(取末尾的 3 前面的数字)构建成新的子集,比如得到 [1,3,2],这也就是为什么上面那棵树是这样的。所以比如 [1,2,3] ,我们得到 [1,2,3] 后不可能回溯成 [1,3] 然后得到 [1,3,2],所以每次的下一层递归,从当前层递归的数组的下标 +1 开始,具体看代码
  •   public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> list = new ArrayList<>();
          backtrack(list, new ArrayList<>(), nums, 0);
          return list;
      }
      
      private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
          //走过的所有路径都是子集的一部分,所以都要加入到集合中
          list.add(new ArrayList<>(tempList));
          for (int i = start; i < nums.length; i++) {
              //做出选择
              tempList.add(nums[i]);
              //递归,i+1 防止重复结果
              backtrack(list, tempList, nums, i + 1);
              //撤销选择
              tempList.remove(tempList.size() - 1);
          }
      }
    
  • 位运算:其实在构建每个子集时都可以看成,每个数都有两种状态,加入子集或者不加入。设加入为 1,不加入为 0,数组长度为 n,就能把每个子集看做 n 位二进制数,那么总个数就是 2n。比如 [1,2,3],每个子集都能看做三位的二进制数,[] 就是每个数都不选即 000,[1,3] 就对应 101。
    请添加图片描述
  • 因此,比如例子 1,我们只需要遍历这 n(该例中为 8) 个数,范围为 0~7, 比如 6 对应为 110,就表示该子集为 [2,3],再比如 3 对应为 011,表示子集 [1,2](因为低位表示数组下标小的数)
  •   public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> res = new ArrayList<>();
          int len = nums.length;
          // 子集个数
          int resCount = 1<<len;
          // i 其实就是每种子集对应的二进制数的十进制
          for(int i=0;i<resCount;i++){
              List<Integer> list = new ArrayList<>();
              // 看是否包含 nums 中某个数
              for(int j=0;j<len;j++){
              	// 如果包含就添加到 list
                  if((i>>j&1)==1)list.add(nums[j]);
              }
              res.add(list);
          }
          return res;
      }
    
  • 非递归:我们先加入一个空集,遍历时 nums 时每次都把 nums[i] 加到之前的子集中构建新子集,遍历完也就得到了全部子集。比如例子 1 我们会依次得到: []->[[],1]->[[],1,2,12]->[[],1,2,12,3,13,23,123]
  •   public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> res = new ArrayList<>();
          res.add(new ArrayList<>());
          for(int num : nums){
              int size = res.size();
              for(int j=0;j<size;j++){
                  List<Integer> tempList = new ArrayList<>(res.get(j));
                  tempList.add(num);
                  res.add(tempList);
              }
          }
          return res;
      }
    
  • 强行递归也可以,其实就是递归形式的循环
  •   public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> res = new ArrayList<>();
          res.add(new ArrayList<>());
          dfs(nums,res,0);
          return res;
      }
      public void dfs(int[] nums,List<List<Integer>> res,int index){
          if(index >= nums.length)return;
          for(int i=0,j=res.size();i<j;i++){
              List<Integer> list = new ArrayList(res.get(i));
              list.add(nums[index]);
              res.add(list);
          }
          dfs(nums,res,index+1);
      }
    
  • 递归:还是上面的思路,我们在构建一种子集时,都可以看做对每个数选或不选。比如 nums:[1,2,3] 选择 12,不选 3,得到 011,也就是说完全可以当做一个二叉树,因为对于每个数只有选或不选两种可能,所以递归部分就写做选择的过程
  •   public List<List<Integer>> subsets(int[] nums) {
          List<List<Integer>> res = new ArrayList<>();
          dfs(res, new ArrayList<>(), nums, 0);
          return res;
      }
      public void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int index){
          if(index == nums.length){
              res.add(new ArrayList<>(list));
              return;
          }
          // 不选,直接继续递归
          dfs(res, list, nums, index + 1);
          // 选择(加入 list)
          list.add(nums[index]);
          // 选完再递归
          dfs(res, list, nums, index + 1);
          // 撤销选择
          list.remove(list.size() - 1);
      }
    
文章来源:https://blog.csdn.net/m0_53256503/article/details/135642746
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。