Does anyone know why this test case yields 2?

• When the input is as below, the expected answer is 2
[1,0]
1

Should it be 1? The first 1 could be 1 and -1. when it is 1, there is one way. But when it is -1, there is no way to sum all the numbers to 1 (-1 + 0), right?

Am I missing something obvious?

• Am I missing something obvious?

Yes you are :-P

• The reason I missed (0 - -1)/(0+1) is because I was using deduction instead of summation along the way. My code was like

helper(nums, start + 1, S - nums[start]) + helper(nums, start + 1, S + nums[start]);

The base code was checking for 0. In this case, the first helper goes like helper(nums, 1, 2). It returns 0 eventually because there is no way for the remaining array to sum up to 2. It happened to pass 99% of the test cases.

When I turned it around using summation, I can easily see (0+1) when 1 is negative. Hence, the result is 2.

• @wuxi.yanhu Uh... no... that's not it.

• What is it ?

I can pass all test cases now using summation though.

• You're missing `+1-0`.

What's your solution now? It doesn't sound right.

• @StefanPochmann
here is the brutal force one Accepted using summation.

``````public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length ==0) return 0;

return helper(nums, 0, 0, S);
}

private int helper(int[] nums, int start, int sum, int target) {
if(start == nums.length){
return sum == target? 1: 0;
}

int ways = helper(nums, start + 1, sum - nums[start], target) + helper(nums, start + 1, sum + nums[start], target);
return ways;

}
``````

Here is my old one using deduction which works most of time but fails this test case.

``````   public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length ==0) return 0;
return helper(nums, 0, S);
}

private int helper(int[] nums, int start, int target) {
if(start == nums.length) return 0;

if (start == nums.length - 1 && nums[start] == Math.abs(target))
return 1;

return helper(nums, start + 1, target - nums[start]) + helper(nums, start + 1, target + nums[start]);

}``````

• Ah, ok. That looks correct. Your "turned it around using summation" and "0+1" sounded like something else.

• @StefanPochmann Sorry for the confusion. What I meant by "turned it around" was from deduction to summation. I was stuck on this for a while because it worked correctly in most cases on paper and passed 99% of the test cases. Because of deduction, I could not see how to make it work when it is -1, 0 going down the recursion stack.

Thanks for looking into it.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.