Python递归实现组合总和2异常：结果列表为空无法正确追加

原代码存在的核心问题 #

• 未排序候选数组：原数组无序，无法有效跳过重复元素，也无法提前剪枝，导致逻辑混乱且可能生成重复组合。
• 直接追加列表引用：self.slack.append(output) 保存的是output的内存引用，后续output.pop()会修改这个引用指向的列表，最终导致结果被清空为[]。
• 未处理重复元素：同一层递归中重复选择相同元素会生成重复结果，没有对应的跳过逻辑。
• 递归返回值冗余：内部递归函数返回self.slack无实际意义，反而可能引发不必要的None值问题。

修正后的代码 #

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.slack = []
        # 排序候选数组，用于去重和剪枝
        candidates.sort()
        
        def rec(start, target, path):
            if target == 0:
                # 保存当前路径的副本，避免后续修改影响结果
                self.slack.append(path.copy())
                return
            if target < 0:
                return
            
            for i in range(start, len(candidates)):
                # 跳过同一层的重复元素，避免生成重复组合
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                # 剪枝：当前元素超过剩余target，后续元素更大，直接终止循环
                if candidates[i] > target:
                    break
                path.append(candidates[i])
                # 递归调用，start设为i+1，确保每个元素仅使用一次
                rec(i+1, target - candidates[i], path)
                path.pop()
        
        rec(0, target, [])
        return self.slack

关键修改说明 #

1. 排序数组：排序后既可以通过相邻元素比较跳过重复值，也能在元素大于剩余target时直接终止循环，减少无效递归。
2. 保存列表副本：使用path.copy()创建当前路径的独立副本存入结果列表，彻底解决后续修改导致结果被清空的问题。
3. 跳过重复元素：通过i > start and candidates[i] == candidates[i-1]判断，跳过同一层递归中的重复元素，避免生成重复组合。
4. 优化递归逻辑：改用循环遍历替代原有的两次递归调用，逻辑更清晰；增加target < 0的剪枝条件，提前终止无效递归。
5. 移除冗余返回值：内部递归函数无需返回结果，仅在找到有效组合时追加到结果列表即可。

测试输入candidates = [10,1,2,7,6,1,5], target = 8，将得到预期输出：[[1,1,6],[1,2,5],[1,7],[2,6]]

内容的提问来源于stack exchange，提问作者117__pushpak raj__