494. Target Sum

Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

  Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

  Constraints:

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• 0 <= sum(nums[i]) <= 1000

• -1000 <= target <= 1000

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    var sum = 0;
    nums.forEach(function(num){
        sum += num;
    });
    if(target>sum || target<-sum) return 0;
    var dp = [];
    dp[0+sum] = 1;
    var maxIndex = sum*2+1;
    nums.forEach(function(num){
        var tmp = [];
        for(var k=0;k<maxIndex;k++){
            if(dp[k] !== undefined && dp[k] !== 0){
                if(tmp[k+num] === undefined){
                    tmp[k+num] = dp[k];
                }else{
                    tmp[k+num] += dp[k];
                }

                if(tmp[k-num] === undefined){
                    tmp[k-num] = dp[k];
                }else{
                    tmp[k-num] += dp[k];
                }
            }
        }
        dp = tmp;
    });
    return dp[target+sum]===undefined?0:dp[target+sum];
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).