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
更多推荐
Leetcode 78 Subsets
发布评论