You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Leetcode 377. Combination Sum IV 回溯法索引实现问题求助

手动索引实现Combination Sum IV回溯解法的疑问

Combination Sum IV是一道经典编程面试题,题目要求如下:

给定一个由不同整数组成的数组nums和一个目标整数target,返回相加和为target的可能组合的数量。每种元素可无限次使用。

该问题的最优解法是动态规划,但我想通过回溯法加深对回溯思想的理解。目前已写出带循环的递归回溯版本且可正常运行,但尝试用手动索引替代循环实现时却无法正常工作,想请教是否可以通过手动索引的方式完成该回溯解法?

可正常运行的循环回溯版本

function combinationSum4 (nums, target, currTotal=[0], nbWays=[0]) {
    
    if (currTotal[0] === target) {
        nbWays[0]++;
        return nbWays[0];
    }
    
    if (currTotal[0] > target) {
        return nbWays[0];
    }

    for (const num of nums) {
        currTotal[0] += num;
        combinationSum4(nums, target, currTotal, nbWays);
        currTotal[0] -= num;
    }
    
    return nbWays[0];
}

我计划用“快索引”和“慢索引”来模拟循环逻辑,以nums=[1,2,3]、target=4为例,回溯过程如下:

0
          i=0 /  
             /   
            1[1]   
       i=0 /     \   
         2[1,1]   \ i=1     
      i=0/         **3[1,2]**
        3[1,1,1]  /  
      /          / i=0
    ...        4[1,2,1]

注意当走到i=1时,需要从0开始重新遍历数组,但我不知道如何在不使用循环的情况下用代码实现这个逻辑,请问这种手动索引的实现方式是否可行?

无法正常运行的手动索引版本

function combinationSum4 (nums, target, currTotal=[0], nbWays=[0], fastIndex=0, slowIndex=0) {
    
    if (currTotal[0] === target) {
        nbWays[0]++;
        return nbWays[0];
    }
    
    if (currTotal[0] > target || slowIndex >= nums.length || fastIndex >= nums.length) {
        return nbWays[0];
    }
    
    const num = nums[fastIndex];
    currTotal[0] += num;
    combinationSum4(nums, target, currTotal, nbWays, fastIndex, slowIndex);
    currTotal[0] -= num;
    combinationSum4(nums, target, currTotal, nbWays, fastIndex+1, slowIndex);

    combinationSum4(nums, target, currTotal, nbWays, 0, slowIndex+1);

    return nbWays[0];
}

内容的提问来源于stack exchange,提问作者nodel

相关产品推荐
方舟 Agent Plan

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

最近更新时间:2026.07.31 11:56:35