leetcode回顾——Subsets 求子集问题

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

示例:

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

题解

首先，考虑给定的数组的子集的个数到底为多少，这里有一个公式，对于一个有n个元素的集合，它的子集个数为2^n + 1，这个时候注意到有一个2^n，于是想到二进制，而正好的是，从0～2^n所对应的二进制数就代表着子集的元素情况：一共集合有n个元素，一共有n个位置可以组合，每个位置上该元素可以出现也可以不出现；因此可以假设二进制的1代表这个数出现，0代表这个数不出现

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        size = int(pow(2, len(nums)))
        hash_n = 1
        while hash_n <= size:
            t = []
            for i in range(len(nums)):
                a = 1 << i
                if a&hash_n:
                    t.append(nums[i])
            ans.append(t)
            hash_n += 1
        return ans