组合总和

Leetcode Link: 39. 组合总和 - 力扣（LeetCode）

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

关键：candi 中的元素都是大于 0 的。 本题属于 可以使用重复元素的组合

解法一

思路： 回溯，但是本题有几个细节点，相比随想录中前面的问题更加复杂

1. 不知道输入有序无序
2. 满足题目条件，不一定就要返回，继续往下走可能还有答案
3. 终止条件必需返回（或者说，必须有一个明确返回的终止条件）
4. 剪枝更加复杂

对于本题来说，上面的 2)，由于可能无序，所以在满足题目要求后，必需还要往下走，因为后面可能还有答案

根据题目，因为都输入都大于 0 的，因此当 target 小于 0 的时候，就可以认定是终止条件可以返回了

对于剪枝，可以这样思考： 由于本题不限制组合的位数，我们假设固定输出 N 位，在有重复的情况下进行选出 N 位的组合（注意是组合），那么只要保证下一位的数字大于等于这一位的数字，就一定能够无遗漏、无冗余的找到所有 N 位的组合。具体怎么证明我不知道，可以用123试一试。

题解：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(tar, stone=-float('inf')):
            nonlocal candidates, res, path
            # 终止条件：tar < 0
            if tar < 0:
                return 
 
            for val in candidates:
                # 剪枝: 以前一位数字为锚点，后面所有的数字都要比大于等于这个数字
                if val < stone: 
                    continue # 不知道有序没序，要continue 
 
                path.append(val)
                # 满足题目要求
                # 注意：满足题目要求不一定要返回，后面可能还有
                if val == tar:
                    res.append(copy.deepcopy(path))
                    path.pop()
                    continue 
 
                backtracking(tar-val, val)
                path.pop()
        
        res = []
        path = []
        backtracking(target)
        return res

解法二

复习的时候想的方法

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        # 当前使用到第i位了
        def bkt(i):
            nonlocal target
            if sum(path) == target:
                res.append(path.copy())
                return
            if sum(path)> target or i == len(candidates):
                return
            
            # 选
            path.append(candidates[i])
            bkt(i)  # 还是第i位，因为可以重复选。
            path.pop()
            # 不选
            bkt(i+1)
        
        bkt(0)
        return res
            

解法三

采用标准的回溯模板

result = []
def backtrack(选择列表, 路径):
    if 满足结束条件:
        result.add(路径)
        return
 
    for 选择 in 选择列表:
        # 做选择
        路径.add(选择)
        将该选择从选择列表移除
        backtrack(选择列表, 路径) # 核心 递归调用之前【做选择】，调用之后【撤销选择】
        # 撤销选择
        路径.remove(选择)
        将该选择再加入选择列表

即添加 for 循环在选择列表里进行选择

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        # 当前使用到第i位了
        def bkt(i):
            nonlocal target
            if sum(path) == target:
                res.append(path.copy())
                return
            if sum(path)> target:
                return
            
            for next_i in range(i, len(candidates)):
                path.append(candidates[next_i])
                bkt(next_i)
                path.pop()
        
        bkt(0)
        return res

启发和联系

一个回溯算法，需要思考的细节问题如下：

1. 何时停止? 即 return，一个回溯算法，必需有一个停止的时候来 return
2. 何时满足题目的要求？ 判断前需要提前 path.append(), 满足要求后需要 path.pop()，并且思考之后是 continue（表示后面可能还有答案）还是 return（后面肯定没有答案）
3. 思考如何剪枝
4. 务必记得维护 path 变量