Java solution with explanation


  • 0
    L

    The simple idea is to try both positive and negative values of an index to see if the solution will fit. The complexity is exponential since it will try all combinations. Memoization may help here. Nonetheless, the solution is:

      private int globalcount;
    
    
    
      public int findTargetSumWays(int[] nums, int S)
      {
        if (nums.length == 0)
        {
          return 0;
        }
        helper(nums, 0, 0, S);
        return globalcount;
      }
    
    
    
      private int helper(int[] nums, int i, int sum, int S)
      {
        if (sum == S && i == nums.length)
        {
          return 1;
        }
        else if (i == nums.length)
        {
          return 0;
        }
        
        if (helper(nums, i + 1, sum + nums[i], S) == 1)
        {
          globalcount++;
        }
        if (helper(nums, i + 1, sum - nums[i], S) == 1)
        {
          globalcount++;
        }
        return 0;
      }
    

Log in to reply
 

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