[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

【解释】 给定一个集合,求该集合的所有子集。 【思路】

思路一、DFS

想象有那么一棵树,初始树的根结点为空(假设为第零层),则没往下一层添加一个元素,树的第几层其子集就会有几个元素。使用树的深度优先遍历就可以得到所有的子集,每回溯一次,就要删除最后一个加入的结点。二刷了,刚开始还是没想出来,很是惭愧。推荐看下这里 的图片,就会很清晰了。

public class Solution {
   public void backtrack(int[] nums,List<List<Integer>> result, ArrayList<Integer> list,int level){
        result.add(new ArrayList<Integer>(list));
        for(int i=level;i<nums.length;i++){//若当前层次没有超过最大高度,继续深度优先遍历,否则执行remove语句
            list.add(nums[i]);
            backtrack(nums,result, list,i+1);//深度优先遍历下一层
            list.remove(list.size()-1);//删除最后加入的结点
        }
    }
     public List<List<Integer>> subsets(int[] nums) {
         List<List<Integer>> result=new ArrayList<List<Integer>>();
         int num=nums.length;
         //当然这里不排序也可以AC,排序从小到大看起来更顺眼?
         Arrays.sort(nums);
         ArrayList<Integer> list=new ArrayList<Integer>();
         backtrack(nums,result, list,0);
         return result;
        }

}

思路二、 迭代法 参考这里 以集合{1,2,3}为例。 初始化:[[]] 第一步:[[],[1]](在上面的结果的子集上添加元素1并上面的集合) 第二步:[[],[1],[2],[1,2]](上第二步结果上每个子集添加元素2并上面的集合) 第三步:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]](…) 代码:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
         List<List<Integer>>  result=new ArrayList<List<Integer>>();
         Arrays.sort(nums);
         List<Integer> list=new ArrayList<Integer>();
         result.add(new ArrayList<>(list));
         for(int i=0;i<nums.length;i++){
             int n=result.size();//先保留size,因为后面的result的size一直在变
             for(int j=0;j<n;j++){
                 list=new ArrayList<Integer>(result.get(j));
                 list.add(nums[i]);
                 result.add(list);
             }
         }
         return result;
    }

}

思路三、位操作 同样参考上面的链接。假设有集合有n个元素,子集的个数为2n−12^{n-1}。可以把这2n−12^{n-1}元素是由n位二进制数组成的集合,每次只要看n位二进制中的哪一位为1,则指定集合包含在子集中。如i=3(011)i=3(011),集合{1,2,3}对应的二进制位为1,2,4 则此时子集为{1,2}。这个方法感觉很神奇,有木有。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        int length=nums.length;
        for(int i=0;i<1<<length;i++){
            List<Integer> result=new ArrayList<>();
            for(int j=0;j<length;j++){
                if((i&(1<<j))!=0)//判断第j为是否为1
                    result.add(nums[j]);        
            }
            results.add(result);
        }
        return results;
        }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习之tensorflow实战篇

python中从str中提取元素到list以及将list转换为str

在Python中时常需要从字符串类型str中提取元素到一个数组list中,例如str是一个逗号隔开的姓名名单,需要将每个名字提取到一个元素为str型的list中...

3183
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十三)

如果是你自己定义函数,函数名要符合变量命名规则,并且不能是系统关键字(在jupyter中,打出系统关键字是绿色的)

782
来自专栏HTML5学堂

操作符与数据类型转换

上一期堡堡给大家讲解了关于JS的基础语法,虽然是一些非常基础的知识,但是它对大家的后期学习奠定了一定的基础。知识像一张网,基础越扎实,网住的鱼就越多,要告诉大家...

2808
来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(七) 常用的类

正文之前 没辙,为了我的一个完整的教程,不得不忍痛继续写一些简单的东西,虽然这些网上都有,但是要纳进我的体系还是需要写进来的,以后自己要看了, 直接就可以看到了...

3306
来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题三(10道)

【编程题】Java编程题三(10道) 【程序21】 题目:求1+2!+3!+...+20!的和 public class lianxi21 { publ...

3426
来自专栏贺贺的前端工程师之路

split的坑-字符串分割

昨天在调代码的时候,遇到了一个很大的坑儿,让我不得不记录下来,莫非是我写js代码太久了的缘故?大概也许可能吧...

853
来自专栏猿人谷

sizeof和strlen的区别

第一个例子:  char *ss="0123456789";    sizeof(ss)=4, ss是指向字符串常量的字符指针。    sizeof(*s...

1818
来自专栏猿人谷

位运算

位运算   位运算是把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1.比如十进制的2转...

1748
来自专栏blackheart的专栏

[C#1] 8-数组

1.数组概述 声明数组: //每个元素初始化为0,虽然数组元素是值类型,但是却是分配在托管堆中的; int[] myArray=new int[100]; //...

1797
来自专栏Java帮帮-微信公众号-技术文章全总结

第三天 引用类型选择结构循环结构【悟空教程】

1758

扫码关注云+社区