组合总和(Python)

代码献上：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        #对数组进行排序，最小值 > target的话，则return back
        
        #组合情况：
        candidates.sort()   #对数组进行排序
        if candidates[0] > target :
            return []
        else:
            ans = []
            #出现重复元素
            def ret(s,array,remain):
                for i in range(s,len(candidates)):
                    c = candidates[i]
                    if remain == c:
                        ans.append(array   [c])
                    elif(remain > c):
                        ret(i,array   [c],remain - c)
                    else:
                        return []
            ret(0,[],target)
        return ans

本题主要用到一种回溯算法的思想，接下来简要介绍一下回溯算法。

回溯法，又名试探法，是一种优选搜索算法，可以理解为试探性搜索算法。在搜索到某一步的时候，如果发现不能满足条件，那么就退回到上一步，在上一步重新选择。

回溯法是以深度优先方式来搜索问题的解，也就是里面的每一步可以理解为一个结点，这些步骤串起来就是一棵树，也就是解空间树。比如第一步只有 1 种做法，第二步有 4 种做法，那么第二步选择一种尝试之后，如果匹配，会假设当前步骤没有问题，继续往第 3 步深入探索，而不是先尝试第二步的其他选择。

当搜索解空间树中的任何一个结点的时候，判断该结点是不是包含问题的解。

如果不包含，那么就把当前的结点以及剩下的节点步骤全部抛弃（也称为剪枝），然后往上一层的结点回溯，也就是退回上一步重新选择（之前的选择走不通）。
如果包含，说明当前结点是可能获取到解的，继续进入下一层子树进行深度优先搜索。
一般来说，回溯法可以有两种做法：

递归：设计思路比较简单，但效率不高。
递推：算法设计相对比较复杂，但效率高。

类似的题目还有：

• 八皇后问题（待更新）
• 机器走迷宫（待更新）
• 0-1背包（待更新）
• 旅行售货员问题（待更新）
• 图的m着色问题（待更新）

这篇好文章是转载于：学新通技术网