Target Sum

Description

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(javascript)

const findTargetSumWays = (nums = [], S) => {
  const memo = {}
  const aux = (index, result) => {
    if (memo[index] !== undefined && memo[index][result] !== undefined) {
      return memo[index][result]
    }
    if (index === nums.length && result !== S) {
      return 0
    }
    if (index === nums.length && result === S) {
      return 1
    }
    memo[index] = memo[index] || {}
    memo[index][result] = aux(index + 1, result + nums[index])
      + aux(index + 1, result - nums[index])
    return memo[index][result]
  }
  return aux(0, 0)
}