leetcode78 -- Subsets (求一个集合的所有的子集,即求幂集)

leetcode78 -- Subsets (求一个集合的所有的子集,即求幂集)

题目


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

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解答

之前做过一道关于C(n,k)的题目,不过那里的数是由n来决定的,这里的数组中的数字可能没有序,不过也没有关系,我先想到的是用之前那道题来做,只需要把k从0遍历到n,然后把对应的全部返回,感觉挺慢的,不过通过测试了。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        for k in range(len(nums)+1):
            ret += self.combine(nums, len(nums), k)
            
        #print(ret)
        return ret        
            
    def combine(self, nums, n, k):
        if k>n or k<0:
            return []
        if k==0:
            return [[]]   
        # 上面是一些special的情况和递归到最后的情况.
        # 从n个元素中先择k个出来,分了两种情况,一种是有最后一个元素的.
        res = self.combine(nums[:n-1], n-1, k-1)    # 这个是有最后的元素的,但是现在得到的是没有的,所以要append[nums[n-1]], 因为现在是从前面的里面选了k-1个. 
        for a in res:
            a.append(nums[n-1])
            
        # 另外一种是没有最后一个元素的,也要放在最后的res里面去.
        for a in self.combine(nums[:n-1], n-1, k):
            res.append(a)

        return res

不过奇怪的是我并没有给数组排序,但是题目要求的是要递增的顺序,但是通过了。。。

  • 第二种解法

都知道如果一个集合的基数是m的话,那么它的幂集的基数是 $2^m$,这是因为长度为$0,1,…,m$的集合的个数分别有$1+C(m,1)+C(m,2)+..+C(m,m)$个。可以利用这种想法来解决这一道题目。

刚开始长度为0的时候,我们只有[], 现在假设数组是[1,2,3], 我们看1,可以得到[], [1],即在空集的上面加了一个1, 然后我们看2,[],[1],[2],[1,2], 这样就变成了4个,所以再把3放进去的时候就变成了8个了。

按照这种非递归的方法写的是


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        res = [[]]
        nums.sort()  # 不用排序也没事儿.
        
        for i in range(len(nums)):
            m = len(res)   # 因为res一直在变,所以要先获得其长度
            for j in range(m):
                temp = res[j][:]    # 要先把以前的copy一份出来,用copy出来的去做改动.
                temp.append(nums[i])
                res.append(temp)
        return res

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦