leetcode [78] 子集

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例:

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

思路：递归子问题，记 子子集 为第一个节点后子集，那么：

子集 = （第一个节点，子子集， 第一个节点和子子集的组合）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums, []]
        
        result = [nums[:1]]
        subs = self.subsets(nums[1:])
        for ss in subs:
            if ss not in result:
                result.append(ss)
        for ss in subs:
            tmp = nums[:1] + ss
            if tmp not in result:
                result.append(tmp)
        return result