LeetCode 组合总和 II题解题目描述给定一个可能包含重复元素的整数数组candidates和一个目标整数target找出candidates中所有可以使数字和为目标target的唯一组合。示例输入candidates [10,1,2,7,6,1,5],target 8输出[[1,7],[1,2,5],[2,6],[1,1,6]]解题思路方法回溯 去重思路使用回溯算法来解决这个问题但需要进行去重处理。首先对数组进行排序使得相同的元素相邻。在选择元素时如果当前元素与前一个元素相同且前一个元素未被选择则跳过当前选择。其他处理方式与组合总和相同。复杂度分析时间复杂度O(n * 2^n)其中 n 是数组的长度。空间复杂度O(n)递归调用栈的深度为 n。代码实现方法回溯 去重# 组合总和 II回溯 去重 def combination_sum2(candidates, target): result [] path [] candidates.sort() used [False] * len(candidates) def backtrack(start, remaining): if remaining 0: result.append(path[:]) return if remaining 0: return for i in range(start, len(candidates)): if i 0 and candidates[i] candidates[i-1] and not used[i-1]: continue path.append(candidates[i]) used[i] True backtrack(i 1, remaining - candidates[i]) path.pop() used[i] False backtrack(0, target) return result # 测试 def test_combination_sum2(): candidates [10, 1, 2, 7, 6, 1, 5] target 8 print(combination_sum2(candidates, target)) # 输出[[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] if __name__ __main__: test_combination_sum2()测试用例测试用例 1基本情况输入candidates [10,1,2,7,6,1,5],target 8输出[[1,7],[1,2,5],[2,6],[1,1,6]]测试用例 2目标为0输入candidates [1],target 0输出[[]]总结组合总和 II 是一个经典的回溯算法问题它可以通过回溯算法和去重处理来高效地解决。回溯 去重的核心思想是对数组进行排序在选择元素时如果当前元素与前一个元素相同且前一个元素未被选择则跳过当前选择。掌握回溯算法和去重处理的使用方法对于解决类似的问题非常重要。