leetcode39. 组合总和

组合总和

#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]选

        利用全局变了存储结果。每个分支都会向分支中存储结果。这样就 不需要考虑每个分支的返回情况。
        '''