18ms java solution


  • 0

    Let numbers with "+" called "in" and numbers with "-" called "out" and the sum of all number called "sum", then

    sum - 2 * out = target
    =>
    2 * sum - 2 * out = target + sum
    =>
    2 * in = target + sum

    public int findTargetSumWays(int[] nums, int S) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                nums[i] *= 2;
            }
            if (Math.abs(sum) < Math.abs(S)) return 0;
            int target = S + sum;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 0; i < nums.length; i++) {
                for (int j = target; j >= 0; j--) {
                    if (j >= nums[i]) dp[j] += dp[j - nums[i]];
                } 
            }
            return dp[target];
        }
    

  • 0
    R

    Can you please explain it in detail?


Log in to reply
 

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