494. Target Sum

Question

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.

Note:

• 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

• Method 1: dfs

  class Solution {
      public int findTargetSumWays(int[] nums, int S) {
          if(nums == null || nums.length == 0) return 0;
          return dfs(nums, S, 0, 0, 0);
      }
      private int dfs(int[] nums, int S, int index, int cur, int start){
          if(index == nums.length){
              return cur == S ? 1 : 0;
          }else{
              return dfs(nums, S, start + 1, cur + nums[start], start + 1)
                      + dfs(nums, S, start + 1, cur - nums[start], start + 1);
          }
      }
  }
  

• Method 2: dp

  class Solution {
      public int findTargetSumWays(int[] nums, int S) {
          int sum = 0;
          for(int num : nums) sum += num;
          if(sum < S) return 0;
          int offset = sum;
          int[][] dp = new int[1 + nums.length][sum + offset + 1];
          dp[0][offset] = 1;
          for(int i = 1; i <= nums.length; i++){
              for(int j = 0; j < sum * 2 + 1; j++){
                  dp[i][j] += (j - nums[i - 1] >= 0 ? dp[i - 1][j - nums[i - 1]]: 0) + (j + nums[i - 1] < 2 * sum + 1 ? dp[i - 1][j + nums[i - 1]]: 0);
              }
          }
          return dp[nums.length][S + offset];
      }
  }
  

Second Time

• Method 1: dp

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

Reference

1. 花花酱 LeetCode 494. Target Sum