组合总和
#python3
class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
# 利用dfs深度优先算法
res = []
def dfs(remain,combo,index): # 利用index来解决这个问题很妙；；；；combo属于临时仓库
if remain==0:
res.append(combo)
return # 没有实际的返回值，而是利用全局变了res存储结果
for i in range(index,len(candidates)): # 分别讨论index=[0,len]的情况
if candidates[i]>remain:
break
dfs(remain-candidates[i],combo+[candidates[i]],i) # list只能跟list相加
candidates.sort()
dfs(target,[],0)
return res
'''
candidates=[2,3,7]
target=7
2+[2,3,7]+[2,3,7]
-----------
3 NO! BECAUSE 7>4
-----------
7
先排序，使用index==0的数字时候，接下来的数值都可以从index==[0,len]选；
index==1的数字时候，接下来的数值都可以从index==[1,len]选；
...
index==i的数字时候，接下来的数值都可以从index==[i,len]选
利用全局变了存储结果。每个分支都会向分支中存储结果。这样就 不需要考虑每个分支的返回情况。
'''
