algorithm - 跟踪子集总和的递归堆栈

递归是如何解决看似复杂的问题的，这一切看起来都很神奇，我读了一篇漂亮地解释了这个算法的论文以下是我的javascript代码：

function allButLast(arr) {
  return arr.slice(0, arr.length - 1);
}

function sSum(arr, sum) {
  //console.log(arr + ':' + sum);
  if (sum === 0) return true;
  if (sum < 0 || arr.length === 0) return false;

  return sSum(allButLast(arr), sum) || sSum(allButLast(arr), sum - arr.slice(-1));
}

/*
sSum([1, 2], 3)
sSum([1], 3) || sSum([1, 2], 1)
sSum([], 3) || sSum([], 2) || sSum([1, 2], 1)
false || sSum([], 2) || sSum([1, 2], 1)
false || false || sSum([1, 2], 1)
false || false || sSum([1], 1) || sSum([1], 1)
false || false || sSum([], 1) || sSum([], 0) || sSum([1], 1)
false || false || false || true || sSum([1], 1) // evaluation stops here
*/
//console.log(sSum([1, 2], 3));  // true

我想了解并调试我在注释中记录的函数调用，我想知道调用是如何执行的，我是否正确地跟踪它？

最佳答案

第一级ssym（1，3）ssum（1，1）
然后sSym（1，3）变成sSym（，3）| | sSum（，2）=>False | | False
而ssum（1，1）变成ssym（，1）ssum（，0）=>false true
您可以添加console.log('sSym(' + allButLast(arr) + ', '+ sum +') || sSum('+ allButLast(arr) + ', '+ (sum - arr.slice(-1)) +')')
在调用ssum返回之前，这将帮助您调试

关于algorithm - 跟踪子集总和的递归堆栈，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38874006/