leetcode 39 组合总和

通过回溯，以及按大小剪枝，因为组合问题所以需要固定一个顺序遍历，因为不同顺序也被视为一个组合。保证path数组中的顺序是升序的。

遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。
注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(path,result,target):
            if target==0:
                result.append(path[:])
                return
            if target<0: 
                return 
            for j in range(len(candidates)):
                if len(path)!=0 and path[-1]>candidates[j]:continue
                path.append(candidates[j])
                dfs(path,result,target-candidates[j])
                path.pop()
        result=[]
        dfs([],result,target)
        return result

Python3 的 [1, 2] + [3] 语法生成了新的列表，一层一层传到根结点以后，直接 res.append(path) 就可以了；
基本类型变量在传参的时候，是复制，因此变量值的变化在参数里体现就行，所以 Python3 的代码看起来没有「回溯」这个步骤。

有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

每次从当前搜索的起点出发，注意因为可以重复从当前节点出发，如果不能重复那么从当前加1的位置出发。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i,path,result,target):
            if target==0:
                result.append(path[:])
                return
            #if target<0: 
                #return 
            for j in range(i,len(candidates)):

                if target-candidates[j]<0:continue
                path.append(candidates[j])
                dfs(j,path,result,target-candidates[j])
                path.pop()
        if len(candidates)==0:
            return []
        result=[]
        dfs(0,[],result,target)
        return result