Difficulty: Medium

Related Topics: Dynamic Programming, Depth-first Search

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:

  1. Input: nums is [1, 1, 1, 1, 1], S is 3\. 
  2. Output: 5
  3. Explanation: 
  5. -1+1+1+1+1 = 3
  6. +1-1+1+1+1 = 3
  7. +1+1-1+1+1 = 3
  8. +1+1+1-1+1 = 3
  9. +1+1+1+1-1 = 3
  11. 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

Language: Java

class Solution {
    private Integer[][] memo;

    public int findTargetSumWays(int[] nums, int S) {
        memo = new Integer[nums.length][2001];

        return dp(nums, nums.length - 1, 0, S);
    }

    // 定义：通过 '+' 和 '-' 使得 nums 里面的元素等于 S 的组合个数
    // dp(i, sum) = dp(i - 1, sum - nums[i]) + 
    //              dp(i - 1, sum + nums[i])
    private int dp(int[] nums, int i, int sum, int S) {
        // 出口
        if(i < 0) return sum == S ? 1 : 0;

        if(memo[i][sum + 1000] != null) return memo[i][sum + 1000];

        return memo[i][sum + 1000] = dp(nums, i - 1, sum - nums[i], S) + 
                                     dp(nums, i - 1, sum + nums[i], S);   
    }
}