Leetcode 78 Subsets

Leetcode 78 Subsets"/>

Leetcode 78 Subsets

Leetcode 78 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],[]
]

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

• 分治：

我们要求[1, 2, 3]的子集，可以分解为[1, 2, 3]本身，[1, 2]、[1, 3]、[2, 3]的子集，同理，[1, 2]可以分解为[1]、[2]的子集，而对于一个元素的子集我们可以直接求解，通过这种思路，我们可以将原问题不断分解，最后进行合并。代码如下：

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:result = [[]]result = self.recursion(nums, result)result = list(self.deque(result, key=lambda x: tuple(x)))return result# 递归求解    def recursion(self, nums, result):length = len(nums)result.append(nums)if length == 1:return resultfor i in range(length):temp = nums.copy()temp.remove(temp[i])self.recursion(temp, result)return result# 列表去重，为了处理不可哈希情况def deque(self, nums, key=None):seen = set()for item in nums:val = item if key is None else key(item)if val not in seen:yield itemseen.add(val)      

使用递归，虽然思路清晰，但是效率并不高

• 迭代算法

对于[1, 2, 3]，首先求[1]与[]的组合，得到[[], [1]]，再求[2]与[[], [1]]的组合，得到[[],[1],[2],[1, 2]]，依次类推，再求[3]与之的组合情况，得到所有的子集，且没有重复。

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:result = [[]]for i in nums:result = result + [[i] + num for num in result]return result