Target Sum does not output the right value

Question

I'm trying to solve the 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

I was able to pass through basic cases but the case with ([0,1], 1) fails.

Trying to understand what am I doing wrong and how I can fix it.

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

Trying to figure out what's going wrong for the second input.

My algorithm is/as follows:

1) Convert the array to a string.

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

Answer 1

Your idea of a DFS could work for small enough input (which the problem's constraints might support) but I'm confused about why convert the number list to a string rather than just perform the DFS directly on the numbers. To find errors in your current method, I would recommend writing intermediate steps to the console to see if they are as you would expect.

Here's some accepted code with the idea of building the possible sums and counting the ways to reach them by including the ways we already have from previous iterations. Hopefully the code makes it clear.

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))