Q78 Subsets

echobingo

发布于 2018-04-25 17:13:56

6830

发布于 2018-04-25 17:13:56

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路：

如果一个集合有 n 个元素，则其所有子集一共有 2^n 个。由此想到二进制的应用。

以上面的例子为例，可以用二进制 1 表示一个数出现在该子集中，二进制 0 表示一个数没有出现在该子集中。比如，如果二进制数是 11，则表示子集 [2,3]（1没有出现）；二进制数是 101，则表示子集 [1,3]（2没有出现）。

因此，我们需要循环 2^n 次，对应 2^n 个子集。将每次循环的数字转化为二进制，然后判断该二进制的每一位是否是 1。如果为 1，则把该位对应的集合中的数字放入到当前子集中，如果是 0 就不放入。

Python实现：

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []
        lens = len(nums)
        for i in range(1 << len(nums)): # 1 << len(nums) 等价于 2 ** len(nums)
            ret.append([])
            # bin(i)[2:].zfill(lens) # 前面默认用 0 填充
            binary = bin(i)[2:].rjust(lens,'0') # 右对齐，前面用 0 填充
            for i in range(len(binary)):
                if binary[i] == '1':  # 1 代表子集中含有该数字
                    ret[-1].append(nums[i])
        return ret

a = [4,7,5]
print(Solution().subsets(a)) # [[], [5], [7], [7, 5], [4], [4, 5], [4, 7], [4, 7, 5]]

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.03.11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法