本文主要是介绍Leetcode 39.组合总和 - Combination Sum - Python - 回溯法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解题思路：
1.由于允许相同数字多次出现，所以相当于需要多次遍历同一个集合，且不知道次数，需要考虑回溯法解题。
2.注意startIndex, 由于252和522属于相同解，所以需要用到startIndex。在每次递归的时候，都向回溯函数中传递starIndex。这样做可以保证两个事情：1.找到相同数字多次出现的解；2.略过相同252，522这种相同解（以2，5，3举例，当第一层循环遍历到5（i=1，此处i就是startIndex），调用递归函数时，继续传入i，即startIndex。那么进入递归函数（第二层循环）时，i依然是1，依然是从5开始遍历，而不是从i=0，集合中的第一个元素2开始遍历。因为2开始的遍历已经结束或正在遍历中，不用再回去重做无用功了）。（看注释）
注意：
1.用python解题时，注意引用。self.result.append(self.path)，这样写会将引用放入self.result,里面的数据会随self.path的改变而改变。应该：self.result.append(self.path[:])，取一个切片。（看注释）
2.将candidates排序+剪枝是常用套路！！常用套路！！常用套路！！
如果是已经排序了，那么for循环中，就是break。
如果没有排过序，那么for循环中，就是continue，因为后面的元素有可能有更小的，且满足target要求的。
代码：
class Solution(object):result = []path = []def combinationSum(self, candidates, target):self.result = []candidate.sort() //排过序了！self.traceBack(candidates, target, 0, 0)return self.resultdef traceBack(self, candidates, target, sum_number, start_index):if sum_number == target:self.result.append(self.path[:]) //注意此处returnif sum_number > target:returnfor i in range(start_index, len(candidates)):if sum_number + candidates[i] > target:break //注意因为排过序了，此处是break，否则写continue!!sum_number += candidates[i]self.path.append(candidates[i])//此处的i作为下一个递归函数的startIndexself.traceBack(candidates, target, sum_number, i) sum_number -= candidates[i]self.path.pop()这篇关于Leetcode 39.组合总和 - Combination Sum - Python - 回溯法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
