javascript - Target Sum 没有输出正确的值

Question

我正在尝试解决目标总和问题 (https://leetcode.com/problems/target-sum/description/)

You are given a list of non-negative integers,
a1, a2, ..., an, and a target, S. Now you have 2 symbols
+ and -. For each integer, you should choose one from
+ and - as its new symbol. Find out how many ways to assign symbols
to make sum of integers equal to target S

我能够通过基本案例，但带有 ([0,1], 1) 的案例失败了。

试图了解我做错了什么以及如何解决。

var findTargetSumWays = function(nums, total) {
    const res = [];
    let str = nums.join('');
    helper(str, '', 0);

    function helper(str, curStr, sum) {
        if(str.length===0) return;
        if(sum + Number(str) === total) {
            res.push(`${curStr}+${str}`);
            return;
        }

        if(sum - Number(str) === total) {
            res.push(`${curStr}-${str}`);
            return;
        }

        for(let i=0; i<str.length; i++) {
            helper(str.substring(i+1), `${curStr}+${str.substring(0, i+1)}`, sum+Number(str.substring(0, i+1)));
            helper(str.substring(i+1), `${curStr}-${str.substring(0, i+1)}`, sum-Number(str.substring(0, i+1)))
        }
    }
    
    return res.length; 
};
console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // Returns correct answer.
console.log(findTargetSumWays([1, 0], 1)); // Expected 2

试图找出第二个输入出了什么问题。

我的算法/如下:

1) Convert the array to a string.

2) Do DFS over numbers E.g: '123456'

Answer 1

您的 DFS 想法可以适用于足够小的输入(问题的约束可能支持)，但我对为什么将数字列表转换为字符串而不是直接对数字执行 DFS 感到困惑。要查找当前方法中的错误，我建议将中间步骤写入控制台以查看它们是否符合您的预期。

这是一些公认的代码，其想法是构建可能的总和并通过包括我们从以前的迭代中已经拥有的方式来计算达到它们的方式。希望代码能说明问题。

function f(nums, S){
  let sums = {0: 1}

  for (let i=0; i<nums.length; i++){
    let newSums = {}
    for (let [sum, ways] of Object.entries(sums)){
      if (nums[i] == 0){
        newSums[sum] = 2 * ways
        continue
      }
      added = Number(sum) + nums[i]
      subtracted = Number(sum) - nums[i]
      newSums[added] = ways + (newSums[added] || 0)
      newSums[subtracted] = ways + (newSums[subtracted] || 0)
    }
    sums = newSums
  }
  return sums[S] || 0
}

var A = [1, 0]
var target = 1
console.log(f(A, target))

A = [1, 1, 1, 1, 1]
target = 3
console.log(f(A, target))