LeetCode【0040】组合总和II

本文目录

1 中文题目
2 求解方法：
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

1 中文题目

给定一个候选人数字编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字编号和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[[1,1,6],
[1,2,5],
[1,7],
[2,6]]

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[[1,2,2],
[5]]

提示：

2 求解方法：

2.1 方法思路

方法核心

使用回溯法搜索所有可能的组合
通过排序实现剪枝和去重
在同一层跳过重复元素

实现步骤

（1）预处理阶段：

对输入数组排序
初始化结果列表
定义回溯函数

（2）回溯搜索过程：

维护当前路径
记录剩余目标值
控制搜索起始位置
处理重复元素

（3）去重处理：

同层重复元素跳过
不同层允许相同值
确保组合唯一性

方法示例

输入示例：candidates = [10,1,2,7,6,1,5], target = 8

执行过程：
1. 首先排序：[1,1,2,5,6,7,10]

2. 回溯搜索过程：

第一层（从索引0开始）：
- 选择1(索引0)：[1], target=7
  第二层（从索引1开始）：
  - 选择1(索引1)：[1,1], target=6
    第三层：[1,1,2], target=4
    第三层：[1,1,5], target=1
  - 跳过1(重复)
  - 选择2：[1,2], target=5
    第三层：[1,2,5], target=0 （找到解）
  - 选择5：[1,5], target=2
    第三层：[1,5,2], target=0 （找到解）
  - 选择6：[1,6], target=1
  - 选择7：[1,7], target=0 （找到解）

- 跳过1(索引1，重复)
- 选择2(索引2)：[2], target=6
  第二层：[2,5], target=1
  第二层：[2,6], target=0 （找到解）

- 选择5(索引3)：[5], target=3
  第二层：[5,2], target=1
  第二层：[5,3], target=0

- 选择6(索引4)：[6], target=2
- 选择7(索引5)：[7], target=1
- 选择10(索引6)：剪枝

最终结果：[[1,1,6], [1,2,5], [1,7], [2,6]]

2.2 Python代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 首先对数组排序，便于后续剪枝和去重
        candidates.sort()
        
        # 存储最终结果
        result = []
        
        def backtrack(start: int, target: int, path: List[int]) -> None:
            """
            回溯函数
            start: 搜索的起始位置
            target: 剩余目标值
            path: 当前路径
            """
            # 找到一个合法解
            if target == 0:
                result.append(path[:])
                return
            
            # 从start开始搜索
            for i in range(start, len(candidates)):
                # 剪枝：如果当前数字大于目标值，后面的数字更大，直接结束
                if candidates[i] > target:
                    break
                    
                # 去重：跳过重复元素，确保每个数字在同一层只被使用一次
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                    
                # 选择当前数字，加入路径
                path.append(candidates[i])
                # 递归：注意起始位置是i+1，因为每个数字只能使用一次
                backtrack(i + 1, target - candidates[i], path)
                # 回溯：移除当前数字
                path.pop()
        
        # 从位置0开始回溯搜索
        backtrack(0, target, [])
        return result