子集

子集

给定一组不含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。

示例

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

题解

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    var target = [[]];
    var n = nums.length;
    if(!n) return target;
    var dfs = (cur, tmp ,deep, limit) => {
        if (tmp.length + (n - cur + 1) < limit) return void 0;
        if(limit === deep) {
            target.push(tmp);
            return void 0;
        }
        for(let i=cur;i<n; ++i){
            dfs(i+1, [...tmp, nums[i]], deep+1, limit);
        }
    }
    nums.forEach((v,i) => dfs(0, [], 0, i+1));
    return target;
};

/**
    dfs(i+1, [...tmp, nums[i]], deep+1, limit);
        1         2          3
      2   3       3      
    ...   ...    ...
    dfs(cur+1, [...tmp, nums[i]], deep+1, limit);
        1         2          3
      2   3     2   3      2   3 
     ... ...   ... ...    ...  ...
 */

思路

在本质上是一个组合问题,以一个长度为4的数组[1, 2, 3, 4]组合2个值为例,每两个组合一个数组可取1组合其数组中之后的值,2与其数组中之后值,3与其数组中之后的值,4与其数组中之后值,即[1, 2][1, 3][1, 4][2, 3][2, 4][3, 4],按照这个思路就需要取出给定数组的1 ~ length长度的组合,首先定义目标数组,空数组是所有的数组的子集,所以将空数组置入,之后取得传入的数组的长度n,如果长度为0则直接返回目标数组,之后定义深度递归遍历,首先进行剪枝,如果当前tmp数组的大小为s,未确定状态的区间[cur,n]的长度为t,如果s + t < limit,那么即使t个都被选中,也不可能构造出一个长度为limit的序列,故这种情况就没有必要继续向下递归,之后判断递归深度如果与limit相等则直接将tmp数组置入目标数组并返回,之后定义一个循环,从cur开始到n进行递归取值,将tmp数组与cur构建一个新数组传递到下一个递归中,之后定义一个循环取得要取得的子集的数组长度,启动递归初始化cur0,深度deep0tmp为一个空数组,limiti+1,递归完成后返回目标数组即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/subsets/

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 组合

    以示例中的值为例,可以认为是一个长度为4的数组[1, 2, 3, 4],每两个组合一个数组可取1组合其数组中之后的值,2与其数组中之后值,3与其数组中之后的值,...

    WindrunnerMax
  • paste命令

    按列合并/tmp/file1.txt与/tmp/file2.txt文件,并追加到/tmp/file3.txt。

    WindrunnerMax
  • find命令

    find命令用来在指定目录下查找文件,任何位于参数之前的字符串都将被视为要查找的目录名,如果使用该命令时,不设置任何参数,则find命令将在当前目录下查找子目录...

    WindrunnerMax
  • Tcpdump Commands

    happy123.me
  • 解读文件描述符

    最近由于机缘巧合,结合最近工作中遇到的一些问题,深入了解了文件描述符(File Descriptor,简称FD,以下使用 FD 称谓)。预计会有两到三篇关于 F...

    技术小黑屋
  • Nacos入门指南02 - 环境搭建

    可惜的是码云中只同步了源码,并没有同步发布页面中的内容,直接在 GitHub 中下载会很慢。

    dys
  • 记录一则DG遭遇ORA-00088的案例

    测试环境:RHEL 5.4 + Oracle 11.2.0.3 DG 现象:起初是在使用DG Broker进行switchover切换测试时,报错ORA-16...

    Alfred Zhao
  • 生成专属于你的人工智能书【3D生成器】

    a-frame 是基于 threejs 的 web AR 库,也可以当 threejs 的简化版本使用,a-frame 只需写 html 标签就可以实现3维空间...

    mixlab
  • python中传值和传地址问题

    在python中,还没有对这个知识点有一个详细的定义,很模糊的说明了,通过下面代码,可以观察出来,什么时候传的是值,什么时候传的是地址

    py3study
  • Consul安装和初步使用

    如果上述安装方式出现了consul not be found的错误,说明环境变量PATH没有配置正确,请返回检查consul安装路径是否包含在PATH中。

    AsiaYe

扫码关注云+社区

领取腾讯云代金券