请教递归实现枚举列表元素累加得目标值n全路径的思路与代码
递归实现可重复选取元素的顺序累加路径求解
核心问题特性说明
和常规的「不重复选元素、不考虑顺序」的组合问题不同,本题的约束是:
- 允许重复选取列表内任意元素,选取次数无限制
- 元素顺序不同算独立路径,比如
1+3和3+1是两条完全不同的有效结果
适配本题的递归基例选型
你之前考虑的「传入列表为空且剩余目标值为0返回0」的设计存在两个核心问题:
- 本题的输入列表是固定常量,递归执行全程不会修改、也不会传入空列表,这个分支根本不会被触发
- 基例的返回值逻辑和需求目标不匹配,我们要收集所有有效路径,不是仅统计路径数量
适配本题的正确基例只需要围绕剩余待累加目标值设计,完全不需要判断列表状态:
- 有效命中基例:当剩余待累加目标值
remain == 0时,说明当前路径的累加和刚好等于目标值,将当前路径存入结果集后递归终止 - 无效剪枝基例:当剩余待累加目标值
remain < 0时,说明之前选的元素累加和已经超过目标值,继续递归也不可能得到有效路径,直接返回终止当前分支
递归执行流程衔接
确定基例后,每一层递归需要传递三个核心状态,保证流程能顺畅衔接:
- 固定不变的可选元素列表
nums - 当前层级还差多少数值需要凑的
remain - 从起点走到当前层级已经选中的元素构成的临时路径
path
每一步的执行逻辑固定为:
- 遍历列表内的每一个可选元素
- 将当前元素加入临时路径
- 计算选择当前元素后的新剩余目标值:
remain - 当前元素 - 带着新的剩余目标值、更新后的临时路径,递归进入下一层
- 递归返回当前层后,将刚才加入路径的元素移除(回溯操作,避免不同分支的路径内容串扰)
参考实现代码
def find_all_valid_paths(nums, target): valid_paths = [] # 递归辅助函数 def helper(remain, current_path): # 基例1:凑够目标,存结果 if remain == 0: valid_paths.append(current_path.copy()) return # 基例2:数值超了,剪枝 if remain < 0: return # 遍历所有可选元素执行选择 for num in nums: current_path.append(num) helper(remain - num, current_path) # 回溯:撤销刚才的选择,回到上一层状态 current_path.pop() helper(target, []) # 按题目要求的等式格式整理输出 return [f"{'+'.join(map(str, path))}={target}" for path in valid_paths] # 验证示例输入 if __name__ == "__main__": test_nums = [1,2,3,4] test_target = 4 res = find_all_valid_paths(test_nums, test_target) print(f"共{len(res)}条有效路径:") for line in res: print(line)
运行验证结果
针对示例输入[1,2,3,4]、目标值4,程序输出恰好和题目给出的7条有效路径完全匹配:
共7条有效路径: 1+1+1+1=4 1+1+2=4 1+2+1=4 1+3=4 2+2=4 2+1+1=4 3+1=4
内容的提问来源于stack exchange,提问作者qua
相关产品推荐
相关产品推荐

