javascript - 递归的子集和 - 我做错了什么？

Question

我正在尝试解决这个问题来练习递归思考:给定一个目标数字和一个数字数组，找出是否存在数组元素的组合总和等于目标数字。我是新来的，我已经尝试了我能想到的一切。我的逻辑有问题还是我忘记了一些简单的事情？这是我的代码:

function findSolution(target, arr){

  function getSum(total, num) {
    return total + num;
  }

  function find(current, push, target, i){
    current.push(push);

    if (current.reduce(getSum) === target){
      return true;
    } else if (current.length >= arr.length){
      return null;
    } else {
      return find(current, arr[i], target, i+1) || 
             find(current, 0, target, i+1);
    }

  }

return find([], 0, target, 0);

return false;
}


console.log(findSolution(23, [4, 6, 10, 1, 3] ));

上面的目标和数组应该返回 true (4+6+10+3) 但它返回 null。 非常感谢你的帮助:)

Answer 1

您需要获取 current 的副本，并且需要返回包含值的数组。不幸的是，您向结果集中添加了太多的零。

因此我建议在调用函数find的地方添加一个值。

您可以在 find 中省略 target，因为您已经对它进行了闭包。

function findSolution(target, arr) {
    function getSum(total, num) {
        return total + num;
    }

    function find(current, i) {
        if (current.reduce(getSum, 0) === target) { // initialValue for empty arrays
            return current;
        }
        if (i >= arr.length) {
            return null;
        } 
        return find(current.concat(arr[i]), i + 1)
            || find(current, i + 1);
    }

    return find([], 0);
}

console.log(findSolution(23, [4, 6, 10, 1, 3]));