子集

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

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

话不多说，show you the code。

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

# 方法一，迭代思路
        res=[]
        for i in nums:
            # 每遇到一个元素
            for j in range(len(res)):
                # 就在现有子集元素的基础上加上该元素，组成新的子集
                res.append(res[j]+[i])
            res.append([i])
        # 最后补上一个空集
        res.append([])
        return res

#方法一-1，依旧是迭代，用列表推导式的方法更pythonic
        res=[[]]
        for i in nums:
            res+=[[i]+j for j in res ]
        return res
# 方法二、递归
        res = []
        n = len(nums)
        
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res

90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

• 本题和上一题的唯一区别就在于 nums会出现重复元素。
• 因此其实做法上只需要增加判断每次迭代或者递归，新的子集元素是否存在于原子集中即可
• 但是由于解集不能包含重复的子集（相同元素的不同序列，如[1,2,2],[2,1,2]），因此在迭代之前必须对nums进行 排序 操作。

  class Solution:
      def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
  # 方法一、递归解法
          if not nums:
              return []
          n = len(nums)
          res = []
          nums.sort()
          def help(idx,tmp_list):
  
              # 判断tmp_list不在原子集才加入
              if tmp_list not in res:
                  res.append(tmp_list)
              for i in range(idx,n):
                  help(i+1,tmp_list+[nums[i]])
          help(0,[])
          return res
  # 方法二、列表推导式法
          res=[[]]
          for i in sorted(nums):
              # 判断[i]+j不在原子集才加入
              res+=[[i]+j for j in res if [i]+j not in res]
          return res
  # 方法三、迭代法
          res=[]
          nums.sort()
          for i in nums:
              # 每遇到一个元素
              for j in range(len(res)):
                  # 判断res[j]+[i]不在原子集才加入
                  if res[j]+[i] not in res:
                  # 就在现有子集元素的基础上加上该元素，组成新的子集
                      res.append(res[j]+[i])
              if [i] not in res:
                  res.append([i])
          # 最后补上一个空集
          res.append([])
          return res

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/11/21/子集/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！