[Leetcode][python]Subsets/Subsets II/子集/子集 II
[Leetcode][python]Subsets/Subsets II/子集/子集 II
蛮三刀酱
发布于 2019-03-26 16:22:56
发布于 2019-03-26 16:22:56
Subsets
题目大意
给定一个由不同数字组成的集合，罗列出该集合的所有子集。
解题思路
见下方代码
代码
纯思路
参考： https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html 举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = [[]]
for num in sorted(nums):
result += [item + [num] for item in result]
return result沿用排列题DFS
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
nums.sort()
for i in range(0, len(nums)+1):
self.k = i
self.combineHelper(0, [], nums)
return self.result
def combineHelper(self, length, temp, list_num):
if length == self.k:
self.result.append(temp[:]) # 需要用切片浅复制出一个新数组
return
for i, num in enumerate(list_num):
temp.append(num)
self.combineHelper(length+1, temp, list_num[i+1:])
temp.pop()Subsets II
题目大意
给定一个由不同数字组成的集合，罗列出该集合的所有子集。 有重复
解题思路
和上一题相同，问题在于如果有重复则会生成多余的子集。 参考：https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html 现在举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。
代码
沿用排列题DFS
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = [[]]
nums.sort() # sort()直接修改原数组，sorted()返回排序后的数组，不修改原数组
temp_size = 0
for i in range(len(nums)):
start = temp_size if i >= 1 and nums[i] == nums[i - 1] else 0
temp_size = len(result) # 每次取到result最后一位，也就是从start一直到最后一位
for j in range(start, temp_size):
result.append(result[j] + [nums[i]])
print result
return result总结
纯思路做法显然效率更高，此题标签还有位运算做法，有空。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录