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

40. 组合总和 II

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

• 从 candidates 里选数
• 每个位置的数只能用一次
• 组合的和等于 target
• 返回所有不重复的组合

核心思路

先排序，再回溯；每个数只能用一次，用 i+1；同一层遇到相同的数，只用一次。

去重的关键规则

同一层递归中，如果当前数和前一个数相同，就跳过。

if i > start and candidates[i] == candidates[i - 1]:
    continue

• i > start：保证是同一层
• == candidates[i-1]：遇到重复数
• continue：这一层不再用它

代码实现

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()  # ① 排序：去重的前提
        res = []
        path = []

        def backtracking(start, cur_sum):
            # 如果当前和等于 target，记录结果
            if cur_sum == target:
                res.append(path[:])
                return
            # 剪枝：当前和已经超过 target
            if cur_sum > target:
                return
            for i in range(start, len(candidates)):
                # ② 去重：同一层不能用相同的数
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                # ③ i + 1：每个数只能用一次
                backtracking(i + 1, cur_sum + candidates[i])
                path.pop()

        backtracking(0, 0)
        return res

131. 分割回文串

目标： 给你一个字符串 s，

• 把它切成若干段
• 每一段都必须是回文串
• 返回所有可能的切分方案。

例子：

s = "aab"
输出：[["a", "a", "b"], ["aa", "b"]]

核心思路

从左往右切字符串，只要当前切出来的子串是回文，就继续往后切。

1. 从下标 start 开始切
2. 枚举所有可能的结束位置 end
3. 如果 s[start:end] 是回文
   • 把它加入当前方案
   • 从 end 继续切
4. 当切到字符串末尾
   • 当前方案就是一个合法答案

代码实现

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []

        def backtracking(start: int):
            # 如果已经切到字符串末尾
            if start == len(s):
                res.append(path[:])
                return
            # 枚举所有可能的切割位置
            for end in range(start + 1, len(s) + 1):
                substring = s[start:end]
                # 只有当 substring 是回文，才继续切
                if substring == substring[::-1]:
                    path.append(substring)
                    backtracking(end)
                    path.pop()

        backtracking(0)
        return res