算法的经典例题（每天一道算法题）

给定一组不含重复元素的整数数组 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 个子集。