Target Sum

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

Approach - Tabulation 1D Array

• We use an array instead of the map below

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int total = 0;
        for (int x : nums) total += x;
        // Early checks
        if (Math.abs(S) > total || (total + S) % 2 != 0) 
            return 0;
        int P = (total + S) / 2;
 
        // 1D DP array for counting subset sums up to P
        int[] dp = new int[P + 1];
        dp[0] = 1;  // one way to make sum 0
 
        // Build up counts
        for (int num : nums) {
            for (int j = P; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[P];
    }
}
 

Approach - Tabulation 1D Map

• We use map for DP and we just add subtract and increase the count, key would be the target and value would be the count
• O(n*m), O(m) m is the sum of all the elements in the array

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0,1);
 
        for (int num: nums) {
            Map<Integer, Integer> next = new HashMap<>();
            for (Map.Entry<Integer,Integer> entry: dp.entrySet()) {
                int total = entry.getKey();
                int count = entry.getValue();
                next.put(total + num, next.getOrDefault(total + num, 0) + count);
                next.put(total - num, next.getOrDefault(total - num, 0) + count);
            }  
            dp = next; 
        }
 
        return dp.getOrDefault(target, 0);
    }
}