给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集),下面我们就来聊聊关于算法的经典例题?接下来我们就一起去了解一下吧!
算法的经典例题
先来看下题目给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
这道题是一道典型的考验递归算法的题目,根据题目可以想到,[1,2,3]的子集是[1,2]里面所有的子集和[1,2]里面所有子集和3的组合加上[3]。
解题
var subsets = function(nums) {
// 长度为1时结束递归
if (nums.length === 1) {
return [[], [nums[0]]]
}
// 如果初始的长度就为0,则直接返回[[]]
if (nums.length === 0) {
return [[]]
}
// 取出最后一个数
const nowValue = nums.pop()
// 剩下的数字做递归,找出剩下数字的所有子集
const childSubs = subsets(nums)
// 对所有子集的长度赋值,因为这里会在原数组上做修改,所以先记录了原数组的长度
const subsLength = childSubs.length
// 循环遍历所有子集
for(let i = 0; i < subsLength; i ) {
// 插入当前数和所有子集组合生成的新的子集
childSubs.push([...childSubs[i], nowValue])
}
// 返回结果
return childSubs
};
时间复杂度 O(N*2^N),生成所有子集,并复制到输出结果中。
空间复杂度 O(N*2^N),这是子集的数量。
对于给定的任意元素,它在子集中有两种情况,存在或者不存在(对应二进制中的 0 和 1)。因此,NN 个数字共有 2^N2N 个子集。
,