【一天一大 lee】子集 (难度:中等)-Day20200920
【一天一大 lee】子集 (难度:中等)-Day20200920
前端小书童
发布于 2020-09-24 14:35:40
发布于 2020-09-24 14:35:40
题目:[1]
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明： 解集不能包含重复的子集。
示例：
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
抛砖引玉
抛砖引玉
递归回溯
使用过递归回溯算法解决过：
- 全排列[2]
- 全排列 II
一句话递归回溯算法的逻辑简要概况就是：
在选择多个原数组的元素组成新成组合时，对于任何一个原数组的元素在新的组合中都可以对其有两种选择形式：当前位置选择或者不选择。
- 本题求一个数组的子集：在递归回溯过程中产生的集合都是数组的子集。
- 解集不能包含重复的子集，递归中需要避免重复的子集出现，维护指针作为递归的层数(或者理解为递归回溯处理了数组元素的指针，指针前为处理过后为未处理)
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
let _result = []
if (nums.length === 0) _result
function helper(index, item) {
if (index === nums.length) {
_result.push([...item])
return
}
item.push(nums[index])
helper(index + 1, item)
// 回溯
item.pop()
helper(index + 1, item)
}
helper(0, [])
return _result
}
位运算解法
从上面的逻辑可以知道，在组成子集时对原数组的元素有选择和不选择两种方式，那么用 0 代码不选择，1 代表选择，那么就可以借助二进制的为元素来枚举子集。
nums = [1,2,3]
二进制 | 子集 | 十进制 |
|---|---|---|
000 | [] | 0 |
001 | [3] | 1 |
010 | [2] | 2 |
011 | [2,3] | 3 |
100 | [1] | 4 |
101 | [1,3] | 5 |
110 | [1,2] | 6 |
111 | [1,2,3] | 7 |
- 二进制为边界：1 << len（nums 长 len）
- 二进制数遍历时子集的枚举：
- 将 1 按位左移原数组索引为与当前枚举的二进制数逐位取与，大于 0 则说明有重叠位
- 有重叠位则说明，在按照此二进制位枚举时当前索引会被选中
var subsets = function(nums) {
let _result = [],
len = nums.length
for (let i = 0; i < 1 << len; ++i) {
let item = []
for (let j = 0; j < len; ++j) {
if (i & (1 << j)) {
item.push(nums[j])
}
}
_result.push(item)
}
return _result
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录