494. Target Sum.md

494. Target Sum

---

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Constraints:

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

---

Solution

• mine
  • Java

    • Dynamic Programming

      Runtime: 8 ms, faster than 80.18%, Memory Usage: 39.2 MB, less than 50.00% of Java online submissions

      //O(2S)time  O(2T)space
      // S = F(0) + ..+ F(len - 1),  F(N) = F(N-1) + nums[i]
      // T = MaxSum = 1000
      public int findTargetSumWays(int[] nums, int S) {
          if (Math.abs(S) > 1000) {
              return 0;
          }
          Arrays.sort(nums);
          int len = nums.length;
          int max = 1000;
          int[][] dp = new int[2][max * 2 + 1];
          //dp[i][S] = dp[i - 1][S - nums[i]] + dp[i - 1][S + nums[i]]
          //nums[0] may be 0
          dp[0][max + nums[0]] = dp[0][max + nums[0]] + 1;
          dp[0][max - nums[0]] = dp[0][max - nums[0]] + 1;
          int sum = nums[0];
          for (int i = 1; i < len; i++) {
              sum += nums[i];
              int r = (i - 1) % 2;
              //[max - sum, max + sum]
              for (int j = max - sum; j <= max + sum; j++) {
                  int res = 0;
                  int t = j - nums[i];
                  if (t >= 0) {
                      res += dp[r][t];
                  }
                  t = j + nums[i];
                  if (t < dp[r].length) {
                      res += dp[r][t];
                  }
                  dp[i % 2][j] = res;
              }
          }
          return dp[(len - 1) % 2][S + max];
      }
      

---

• the most votes
  • link with explanation. Runtime: 2 ms, faster than 94.95%, Memory Usage: 36.9 MB, less than 97.66% of Java online submissions

    // O(L * ((s + Sum) * L / 2 - Sum)) → O(L * L * Sum)time    time  O((s + Sum) / 2) → O(Sum) space
    // Sum = sum(nums)  L = len(nums)
    public int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        // sum(P) + sum(N)= sum(nums)
        // the problem same like: sum(P) - sum(N) = target   
        // so  sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
        // 2 * sum(P) = target + sum(nums)
        // so sum(P) must be even
        return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1); 
    }   
    
    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n]; 
        return dp[s];
    }
    

---