难度: 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注意：本题与主站 40 题相同： https://leetcode-cn.com/problems/combination-sum-ii/
运行时间: 31 ms
内存: 16.2 MB
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
path = []
candidates.sort()
def backtrancking(startIndex, total):
# 终止条件
if total == target:
result.append(path[:])
return
elif total > target:
return
for i in range(startIndex, len(candidates)):
# if i > 0 and candidates[i] == candidates[i-1]:
# break
if i > startIndex and candidates[i] == candidates[i-1]:
continue
total += candidates[i]
if total > target:
break
path.append(candidates[i])
backtrancking(i+1, total)
path.pop()
total -= candidates[i]
backtrancking(0, 0)
return result
此题解采用回溯算法解决组合总和问题，关键在于避免重复组合和过滤不合适的路径。首先，将输入数组排序，这有助于后续去重以及提前终止不可能的路径。回溯的过程从数组的起始位置开始，并追踪当前组合的总和。对于每一个元素，算法首先检查是否与前一个元素相同，以避免生成重复的组合。若元素可加入当前路径，算法将其添加到路径中，并递归调用自身，继续探索后续元素。一旦路径中的数字总和超过目标值，或成功匹配目标值，则递归终止。
时间复杂度: O(2^n)
空间复杂度: O(n + 解的数量)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
path = []
candidates.sort()
def backtrancking(startIndex, total):
# 如果当前总和等于目标值，添加到结果中
if total == target:
result.append(path[:])
return
# 如果当前总和超过目标值，剪枝
elif total > target:
return
# 遍历所有可能的选择
for i in range(startIndex, len(candidates)):
# 跳过重复元素以避免重复的组合
if i > startIndex and candidates[i] == candidates[i-1]:
continue
# 尝试包括当前元素
total += candidates[i]
# 如果当前总和超过目标值，则停止当前分支
if total > target:
break
# 选择当前元素，继续递归
path.append(candidates[i])
backtrancking(i+1, total)
# 回溯，撤销选择
path.pop()
total -= candidates[i]
backtrancking(0, 0)
return result
在回溯算法中对候选数组进行排序主要有两个目的：一是为了方便去重，二是为了优化性能。排序后，相同的元素会被集中在一起，这使得在深度优先搜索的过程中，可以通过简单的比较相邻元素来避免选择重复的组合。此外，排序后的数组可以更早地终止搜索：如果当前组合的总和已经超过目标值，由于数组是有序的，后续的元素只会让总和更大，因此可以立即停止这一分支的搜索，从而减少不必要的计算，提高算法效率。
这种方法通常在候选数组已经排序的情况下是有效的，因为只有在数组有序时，相同的元素才会排列在一起，从而通过比较当前元素与前一个元素是否相同来避免重复。如果候选数组未排序，这种方法则会失效。此外，这种去重策略仅在避免在相同的递归层级上使用重复元素时有效，不影响不同层级间的元素选择。因此，在实现时需要确保跳过重复元素的条件仅在当前层级有效，即 `if i > startIndex and candidates[i] == candidates[i-1]`。
这种即时剪枝的策略可以显著提高算法的效率。在回溯过程中，一旦当前的组合总和已经超过目标值，继续添加更多元素只会使总和进一步增大，这明显是无效的。通过立即终止这一路径的搜索，可以避免进行无效的递归调用，从而减少执行时间和计算资源的消耗。这种策略尤其在目标值相对较小而候选数组中包含较大数字时非常有效，可以快速地排除大量不可能满足条件的组合。