【Leetcode】【python】Subsets Subsets II 子集 子集 II

Subsets

题目大意

给定一个由不同数字组成的集合,罗列出该集合的所有子集。

解题思路

见下方代码

代码

纯思路

参考:
https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html
举个例子,集合[1]有[[],[1]]两个子集,当向其中添加一个元素时,[1,2]有[[],[1],[2],[1,2]]四个子集,可以看出来,在新添加一个元素的时候,是在原来子集的基础上,添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的,要先把所有元素都排序。

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

总结

纯思路做法显然效率更高,此题标签还有位运算做法,有空。