Does anyone know why this test case yields 2?


  • 0
    W

    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?


  • 0

    @wuxi.yanhu said in Does anyone know why this test case yields 2?:

    Am I missing something obvious?

    Yes you are :-P


  • 0
    W

    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.


  • 0

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


  • 0
    W

    What is it ?

    I can pass all test cases now using summation though.


  • 0

    You're missing +1-0.

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


  • 0
    W

    @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]);
    
    }

  • 0

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


  • 0
    W

    @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.


Log in to reply
 

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