Leetcode39:组合总和——回溯

题目

https://leetcode-cn.com/problems/combination-sum/

做回溯题就像见老同学，你觉得它还像以前一样简单，但是你错了😭

题解

搜索回溯

思路：对于candidates中的每一个数你有两个选项，要么选，要么不选。所以回溯的过程是一颗二叉树，用idx表示下标，左子树表示选择第idx个数放入路径，右子树不选择。如果不选择，下一次是idx+1，如果选择，下一次仍然是idx，这样可以做到重复选择一个数，但最终结果不会有数字相同但顺序不同的情况。

先看代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        def backtrack(target, idx):
            if idx > len(candidates)-1:
                return
            print("tar",target,"n",candidates[idx],"path",path)
            
            if target == 0:
                res.append(path.copy())
                return
            
            # 不选择
            backtrack(target, idx+1) 
            # 选择
            if target-candidates[idx]>=0:
                path.append(candidates[idx])
                backtrack(target-candidates[idx], idx)
                path.pop()

        backtrack(target, 0)
        return res

标准的回溯模板，但又充满了细节：

• return要放在合适的位置
• 不选择的时候idx+1，选择的时候idx不+1

再看这张图就能理解了：