原题地址：子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解答
[]的子集为[[]]，后面每追加一个元素时，对应的子集就会在原子集的每个元素上追加该元素，并与原子集合并为新的子集。如[1]的子集为[[],[1]]，而[1,2]则在该子集的每个元素中追加了元素2，并与原子集为合并为新子集[[],[1],[2],[1,2]]。
根据该思路实现的代码为：
/**
* @param {number[]} nums
* @return {number[][]}
*/
const subsets2 = function(nums) {
// []的子集为[[]]
let result = [[]];
for (let i = 0; i < nums.length; i ++) {
// 数组中追加一个元素时，子集就在原子集的每个元素中追加该元素
let temp = result.map(item => [...item, nums[i]]);
// 原子集与追加元素后的子集合并为新的子集
result = [...result, ...temp];
}
return result;
};
测试：
let start = new Date();
const test = subsets2;
/**
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ]
]
*/
console.log(test([1,2,3]));
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 结果集的长度为$2^N$，每个都需要一次处理，时间复杂度为$O(2^N)$
空间复杂度： 空间复杂度为$O(2^N)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 28,2019