39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取

说明：
所有数字（包括 target）都是正整数
解集不能包含重复的组合

示例 ：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路1

回溯

这是一道典型的回溯问题，dfs回溯思路如下

• 对于排序后的candidates，从左到右遍历一次，取出第i个元素
• 更新已经被取出的元素列表visited_list + 更新target值为new_target
• 回溯出口：如果target为0，结算visited_list并返回；如果target < 0，直接return
  以上是未做剪枝的最朴素写法

# 回溯
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        visited_list = []
        def backTracking(candidates, target, visited_list):
            if target == 0:
                res.append(visited_list[:])
            if target < 0:
                return 
            for i in range(len(candidates)):
                visited_list.append(candidates[i])
                new_target = target - candidates[i]
                # dfs
                backTracking(candidates[i:], new_target, visited_list)
                # 状态恢复
                visited_list.pop()
        
        backTracking(candidates, target, visited_list)
        return res

思路2

递归做法

• 对于排序后的candidates，从左到右遍历一次，取出第i个元素，更新target值为new_target
• 这时问题转换为了规模更小的同类问题，即candidates[i:]和new_target下的问题。这里就产生了规模缩减的转移式子
• 那么就可以考虑用递归的方式不断缩小target的值，
• 我们要保证递归函数helper接受的参数target必须大于等于0。如果target为0，到达递归出口

### 递归做法 ###
# 对于排序后的candidates，从左到右遍历一次，取出第i个元素，更新target值为new_target
# 这时问题转换为了规模更小的同类问题，即candidates[i:]和new_target下的问题
# 那么就可以考虑用递归的方式不断缩小target的值，
# 我们要保证递归函数helper接受的参数target必须大于等于0。如果target为0，到达递归出口

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        
        # 用递归做
        def helper(candidates, target):
            # 递归出口
            res = []
            if target == 0:
                res.append([])
                return res
            
            for i in range(len(candidates)):
                ele_took = candidates[i]
                new_target = target - ele_took
                # 剪枝
                if new_target < 0:
                    break
                for l in helper(candidates[i:], new_target):
                    res.append([ele_took] + l)
            return res
        
        return helper(candidates, target)

小结

【带返回值的递归】是，【从递推的角度看待问题】，只关心下一规模问题的解，假设得到了下一规模问题的解，推导当前规模问题的解就迎刃而解，本质思想和dp是一致的--不同规模问题的状态转移，如果再保存中间结果就是dp的逆过程了

回溯是【不带返回值的递归】，它从【宏观的整体的角度】看待问题，把一个问题所有可能的解走完，并在来到叶子结点时利用全局变量完成结算。回溯是直接解决整一个问题的思路，而不是解决一个个同类子问题来简化当前问题的思路