leetcode 39. 组合总和 python

题目描述：

题解一：

1.res保存最终解，path记录当前组合，sum记录当前path数字之和。

2.在dfs函数中，如果当前sum与target相等，则说明找到一个结果，将path加入res（需要判断res中是否已经存在和path相同的组合）。

如果当前sum小于target则从candidates中选择candidates[i]加入path，同时更新sum，然后再次调用dfs函数。

class Solution(object):
    def combinationSum(self, candidates, target):
        res = []
        path = []
        n = len(candidates)
        sum = 0
        def dfs(candidates,target,path,res,sum):
            for i in range(n):
                if sum==target:
                    newpath = sorted(path[:])
                    if newpath not in res:
                        res.append(newpath)
                    return
                if sum 
 
 题解二（加剪枝）：
 
参考：https://segmentfault.com/a/1190000023954685
 
在考虑下一个选择的数字时，如果之前考虑过就不用重复。
 
 
class Solution(object):
    def combinationSum(self, candidates, target):
        res = []
        path = []
        n = len(candidates)
        sum = 0
        def dfs(idx,sum):
            if sum == target:
                res.append(path[:])
                return
            for i in range(idx,n):
                if sum 
 
 感觉剪枝没有统一的思路，需要根据题目确定，从结果来看，剪枝可以有效减少运行时间。