-
Notifications
You must be signed in to change notification settings - Fork 13
/
Copy path078.子集.py
69 lines (56 loc) · 1.87 KB
/
078.子集.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# 递归
class Solution(object):
def subsets(self, nums):
# 终止条件,返回空集
if not nums:
return [[]]
# 获取剩余数组的子集
sub = self.subsets(nums[1:])
# 将第一个元素添加到所有子集中构成新的子集
return [([nums[0]] + s) for s in sub] + sub
# 迭代
class Solution2(object):
def subsets(self, nums):
# 初始化结果数组
res = [[]]
for num in nums:
# 每次迭代将新的数添加到已有子集中构成新的子集
res += [v+[num] for v in res]
return res
# 回溯
class Solution3(object):
def subsets(self, nums):
def find(nums, index, output):
# 每一个新的数组都是子集,可直接添加到全局数组
res.append(output)
# 遍历数组
for i in range(index, len(nums)):
# 通过索引控制可取数组元素
find(nums, i + 1, output + [nums[i]])
res = []
find(nums, 0, [])
return res
# 回溯
class Solution4(object):
def subsets(self, nums):
def find(nums, index, output, res):
res.append(output)
for i in range(index, len(nums)):
# 先更新输出数组,递归回溯后再弹出新值,还原输出数组,搜索下一种情况
output.append(nums[i])
find(nums, i + 1, output, res)
output.pop()
res = []
find(nums, 0, [], res)
return res
# 回溯
class Solution5(object):
def subsets(self, nums):
def find(nums, output):
res.append(output)
for i in range(len(nums)):
# 数值数组和输出数组元素动态更新
find(nums[i+1:], output + [nums[i]])
res = []
find(nums, [])
return res