题目链接
难度：中等 类型：深度优先搜索
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
示例1
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例2
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解题思路
典型的深度优先搜索，每次加入一个数nums[i]，target就更新为target-nums[i]
搜索结束的条件:
- target<0,这条路径的和不为target，放弃
- target==0, 这条可以，收入囊中
代码实现
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
length = len(candidates)
res = []
def dfs( target, index, maybe):
if target < 0:
return
if target == 0:
res.append(maybe)
return
for i in range(index, length):
dfs(target-candidates[i], i, maybe+[candidates[i]])
dfs(target, 0, [])
return res
