子集
子集
WindRunnerMax
发布于 2020-09-22 02:25:37
发布于 2020-09-22 02:25:37
代码可运行
运行总次数：0
代码可运行
子集
给定一组不含重复元素的整数数组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构建一个新数组传递到下一个递归中，之后定义一个循环取得要取得的子集的数组长度，启动递归初始化cur为0，深度deep为0，tmp为一个空数组，limit为i+1，递归完成后返回目标数组即可。
每日一题
https://github.com/WindrunnerMax/EveryDay参考
https://leetcode-cn.com/problems/subsets/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-09-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
推荐阅读
相关推荐
【leetcode刷题】20T41-子集
更多 >
腾讯云开发者
