【进阶篇 - Day 36】 2020-12-06 位运算系列（07. 高频面试题 )

题目描述

入选理由

1.考察大家对位运算的灵应用，有的时候解题用位运算这种“奇淫巧计”会有很不错的效果

题目描述

78. 子集 (opens new window)

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

我的回答

https://github.com/leetcode-pp/91alg-2/issues/62#issuecomment-739622761

解法一

时空复杂度

时间复杂度：O(n*n^2)

空间复杂度: O(n^2)

 */
var subsets = function (nums) {
    let ans = []
    for (let i = 0; i < nums.length; i++) {
        let length = ans.length
        for (let j = 0; j < length; j++) {
            let newChild = [...ans[j], nums[i]]
            ans.push(newChild)
        }
        ans.push([nums[i]])
    }
    ans.push([])
    return ans
};

解法二

时空复杂度

时间复杂度：O(n* 2^n)

空间复杂度: O(n)

var subsets = function (nums) {
    let ans = []
    let n = nums.length
    for (let i = 0; i < (1 << n); ++i) {
        const t = []
        for (let j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                t.push(nums[j])
            }
        }
        ans.push(t)
    }
    return ans
};

参考回答

• [官方题解](https://github.com/leetcode-pp/91alg-2/blob/master/solution/advanced/d36 bit.md)