You need to enable JavaScript to run this app. 请教递归实现枚举列表元素累加得目标值n全路径的思路与代码
优惠活动
大模型
产品
解决方案
定价
更多

请教递归实现枚举列表元素累加得目标值n全路径的思路与代码

递归实现可重复选取元素的顺序累加路径求解

核心问题特性说明

和常规的「不重复选元素、不考虑顺序」的组合问题不同,本题的约束是:

  • 允许重复选取列表内任意元素,选取次数无限制
  • 元素顺序不同算独立路径,比如1+3和3+1是两条完全不同的有效结果

适配本题的递归基例选型

你之前考虑的「传入列表为空且剩余目标值为0返回0」的设计存在两个核心问题:

  1. 本题的输入列表是固定常量,递归执行全程不会修改、也不会传入空列表,这个分支根本不会被触发
  2. 基例的返回值逻辑和需求目标不匹配,我们要收集所有有效路径,不是仅统计路径数量
    适配本题的正确基例只需要围绕剩余待累加目标值设计,完全不需要判断列表状态:
  • 有效命中基例:当剩余待累加目标值remain == 0时,说明当前路径的累加和刚好等于目标值,将当前路径存入结果集后递归终止
  • 无效剪枝基例:当剩余待累加目标值remain < 0时,说明之前选的元素累加和已经超过目标值,继续递归也不可能得到有效路径,直接返回终止当前分支

递归执行流程衔接

确定基例后,每一层递归需要传递三个核心状态,保证流程能顺畅衔接:

  1. 固定不变的可选元素列表nums
  2. 当前层级还差多少数值需要凑的remain
  3. 从起点走到当前层级已经选中的元素构成的临时路径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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.07 06:45:05