Target Sum


  • 0

    Click here to see the full article post


  • 0
    D

    The animation is not very intuitive. Can someone explain the 2D DP solution?


  • 0
    J

    It's not good to use the constrain such as 1000, 2000

    • It's may be good for online test but not good for coding interview or in practice.

  • 0
    U

    for approach 2, the space complexity should be O(nl) due to "memo"


  • 0

    The line of int count = 0 in the code of Approach 2 is useless.


  • 0
    J

    Here is another solution, initially assign + to every number, then use dp to determine how many combination of flips from + to - are there to reach S.

    class Solution {
    public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    for (int n: nums) sum += n;
    if (sum < S || (sum - S) % 2 == 1) return 0;
    int target = (sum - S) / 2;
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 0; i < nums.length; i++) {
    for (int j = target; j >= nums[i]; j--) {
    dp[j] += dp[j - nums[i]];
    }
    }
    return dp[target];
    }
    }


  • 0
    Z

    If the target S is -10000, the approach 2 throw array outbound error. It should test whether S > 1000 || S < -1000, if so, return 0.


Log in to reply
 

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