39. 组合总和
# 题目描述
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
# 样例
Input:candidates = [2,3,6,7], target = 7,
Output:
[
[7],
[2,2,3]
]
Input:candidates = [2,3,5], target = 8,
Output:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 题目解析
本题在 216. 组合总和 III(Medium) 的基础上,放宽了非重复数字的约束条件。其实更加简单了。
# Python 代码示例
def backtracking(candidates, target, cur, ans, tmp):
if sum(tmp) == target:
ans.append(tmp[:])
return
elif sum(tmp) > target:
return
for i in range(cur, len(candidates)): # 从 cur 开始,可以避免走回头路
tmp.append(candidates[i])
backtracking(candidates, target, i, ans, tmp) # cur 从 i 开始相当于 可以重复
tmp.pop()
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
backtracking(candidates, target, 0, ans, [])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54