组合总和
题目要求
解题思路
思路分析：根据示例分析1：输入：candidates = [2,3,6,7]，target =7
- 候选数组中有
2，如果找到了组合总和为7-2=5的所有组合，再在之前加上2，就是7的所有组合； - 同理考虑
3，如果找到了组合总和为7-3=4的所有组合，再在之前加上3，就是7的所有组合，依次这样子找下去。
基于上面的想法，可以画出树形图。建议大家自己在纸上画出这棵树，这类问题都需要先画出树形图，然后编码实现。
编码通过深度优先遍历实现，使用一个列表，在深度优先遍历变化过程中，遍历所有可能的列表并判断当前列表是否符合题目要求，完成[回溯]
难点：出现重复解
产生重复解的原因是，在每个节点，做减法，展开分支的时候，由于题目中说 每一个元素可以重复使用，我们会考虑所有的候选数，因此出现了重复的列表。
一种天然的想法就是使用哈希表的天然去重的功能，但是实际编写代码的时候，会发现存在比较大的困难。
回过头思考，可不可以在搜索的时候就实现去重呢？答案必然是可以的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候，就需要按照某种顺序搜索。具体的做法是：每次搜索的时候，设置下一轮搜索的起点
如图。即：从每一层的第2个节点开始，都不能再搜索产生同一层节点已经使用过的candidate里的元素。
代码
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates,begin,size,path,res,target):
# 终止条件
if target<0:
return
if target==0:
res.append(path)
return
# 继续回溯
for index in range(begin,size):
dfs(candidates,index,size,path + [candidates[index]],res,target- candidates[index])
size = len(candidates)
if size ==0:
return []
res=[]
path=[]
dfs(candidates,0,size,path,res,target)
return res
复杂度分析
时间复杂度：
空间复杂度：
