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
相关产品推荐
相关产品推荐

