LC40. 组合总和 II

题目描述

给定一个数组 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]]

思路解析

核心思路：先排序，然后使用回溯法（DFS）遍历所有可能的组合。关键点：1. 排序是为了方便剪枝和去重；2. 每个数字只能使用一次，所以递归时从下一个索引开始；3. 去重：同一层递归中，如果当前数字与前一个数字相同，且前一个数字未被使用（即跳过），则跳过当前数字，避免产生重复组合。易错点：忘记排序或去重逻辑错误。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈深度）。