算法题解：组合总和、组合总和 II 及分割回文串

39. 组合总和

目标： 给你一个数组 candidates（没有重复数），再给一个目标值 target。

• 从 candidates 里选数（可以重复选同一个数）
• 让选出来的数之和等于 target
• 返回所有可能的组合

例子：

candidates = [2, 3, 6, 7], target = 7
结果：[[2, 2, 3], [7]]

核心思路与剪枝

不停地往组合里加数，只要和没超过 target 就继续试，等于 target 就记下来，超过就停。

1. 用一个 path 记录当前选了哪些数
2. 用一个 cur_sum 记录当前和
3. 每一步从 candidates 里选一个数（⚠️ 可以重复选同一个数）
4. 三种情况
   • cur_sum == target → 存结果
   • cur_sum > target → 这条路不行，停
   • < target → 继续选

代码实现

① '可以重复使用'指的是什么？

当前选中的这个数，下一层还能不能再选一次？能 → 递归传 i；不能 → 递归传 i + 1

② '组合不能有重复'是怎么保证的？

不允许回头选更小的下标，所以 for 循环从当前 start 也就是 i 开始，永远不从 0 重新选。

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []

        def backtracking(start, cur_sum):
            # 如果当前和等于 target，记录结果
            if cur_sum == target:
                res.append(path[:])
                
            
             cur_sum > target:
                
            
             i  (start, (candidates)):
                path.append(candidates[i])
                
                backtracking(i, cur_sum + candidates[i])
                path.pop()

        backtracking(, )
         res