难度: Medium
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30运行时间: 116 ms
内存: 14.8 MB
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates.sort()
def backtrack(path, start):
s = sum(path)
if s == target:
ans.append(list(path))
if s >= target:
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(path, i+1)
path.pop()
backtrack([], 0)
return ans
这个题解使用了回溯搜索的方法来找到所有满足条件的组合。首先将候选数组排序，然后从数组的第一个元素开始，通过递归不断尝试将当前元素加入路径中，并继续搜索剩余元素，直到路径和等于目标值时将当前路径加入结果集。搜索过程中，如果路径和已经大于等于目标值，则可以提前终止搜索。此外，为了避免生成重复的组合，在每一层递归时，如果当前元素与上一个元素相同，则跳过该元素，以确保每个元素只使用一次。
时间复杂度: O(n * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates.sort() # 对候选数组进行排序
def backtrack(path, start):
s = sum(path)
if s == target:
ans.append(list(path)) # 找到满足条件的组合，加入结果集
if s >= target:
return # 路径和已经大于等于目标值，提前终止搜索
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue # 跳过重复元素，避免生成重复组合
path.append(candidates[i]) # 将当前元素加入路径
backtrack(path, i+1) # 递归搜索剩余元素
path.pop() # 回溯，移除当前元素
backtrack([], 0) # 从第一个元素开始搜索
return ans
在回溯过程中，如果当前路径的和已经大于目标值，继续添加更多的元素只会使路径和更大，从而无法达到目标值。因此，一旦路径和超过目标值，可以立即停止当前路径的进一步搜索，避免无效的计算，这样做可以提高算法的效率。
在排序后的数组中，相同的元素会排列在一起。在递归过程中，如果在同一层递归中连续遇到相同的元素，只考虑这些元素的第一个，并跳过后续的相同元素可以避免生成重复的组合。例如，对于数组 [1,1,2]，在第一个1被加入路径后，第二个1在同一层递归中就会被跳过，这样就只会生成不包含重复组合的所有可能组合。
是的，递归深度过大有可能导致栈溢出，尤其是在处理大数据量或者递归深度特别深的情况下。为了避免栈溢出，可以考虑使用迭代的方式来代替递归，或者在编程语言支持的情况下增加递归调用栈的大小。还有一种方法是使用尾递归优化，尽管这依赖于编程语言的编译器是否支持尾递归优化。
排序候选数组是为了更方便地处理重复元素和提早终止无效的搜索路径。首先，排序使得相同的元素聚集在一起，便于在递归过程中识别和跳过重复的元素，从而避免生成重复的组合。其次，排序后的数组可以更容易地判断当前路径的和是否已经超过目标值，如果超过则可以立即停止进一步的搜索。这个步骤对于提高算法的效率和减少不必要的计算是非常有帮助的。