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

Try this Problem on your own or check similar problems:

1. Expression Add Operators

Solution:

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
        sum += nums[i];
    }
    if(target > sum || (sum + target) % 2 == 1)  return 0;

    int sumPositive = Math.abs((sum + target)) / 2;

    int[] dp = new int [sumPositive + 1];
    dp[0] = 1;

    for(int n : nums){
        for(int j = sumPositive; j >= n; --j){
            dp[j] += dp[j-n];
        }
    }

    return dp[sumPositive];
}

Time/Space Complexity:

• Time Complexity: O(n*S) where S == sumPositive
• Space Complexity: O(S)

Explanation:

We defined approach to DP questions in Climbing Stairs where we have 6 step framework on how to solve any DP problem. So, let’s break down this problem into those steps:

• Category: We can either choose a positive or negative version of each number so it’s a 0/1 Knapsack problem with a twist that we have to choose each number (item).
• States: we need to track currentSum and our position in the array (on which item we are and what’s the currentSum).
• Decision: we either keep a positive or negative version of the item.
• Base case: we reach the end of array which holds our items and we either have a matching target and currentSum or we don’t.

Now for the last two steps we first code up brute force solution and then try to iteratively optimize it:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return helper(nums, 0, 0, target);
    }

    private int helper(int[] nums, int index, int currentSum, int target){
        if(index == nums.length && currentSum == target) return 1;
        if(index == nums.length) return 0;

        int addition = helper(nums, index + 1, currentSum + nums[index], target);
        int subtraction = helper(nums, index + 1, currentSum - nums[index], target);

        return addition + subtraction;
    }
}

But the complexity of this solution is O(n) for space complexity (because of the recursion stack) and time complexity O(2^n) (at each step for n steps we have 2 calls). How do we reduce the complexity, well we know that our painpoint is time complexity so we can shift a bit of responsibility/cost to the space. We can use memoization (note different than memorization), we can store expensive recursion calls in auxiliary data structure (often variables like this are called memo) like hashmap, hashset and similar. This helps us to only calculate value for the subproblem once and every other time retrieve the value from the memo (you can think of it as cache for expensive operations):

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Map<Tuple, Integer> memo = new HashMap<>() {};
        return helper(nums, 0, 0, target, memo);
    }

    private int helper(int[] nums, int index, int currentSum, int target, Map<Tuple, Integer> memo){
        if(index == nums.length && currentSum == target) return 1;
        if(index == nums.length) return 0;


        Tuple key = new Tuple(index, target - currentSum);
        if(memo.containsKey(key)){
            return memo.get(key);
        }

        int addition = helper(nums, index + 1, currentSum + nums[index], target, memo);
        int subtraction = helper(nums, index + 1, currentSum - nums[index], target, memo);

        int total = addition + subtraction;

        memo.put(new Tuple(index, target - currentSum), total);
        return total;

    }

    class Tuple {
        public Tuple(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            int hash = 17;
            hash = 31 * hash + this.x;
            hash = 31 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) return true;
            if (other == null) return false;
            if (this.getClass() != other.getClass()) return false;
            Tuple that = (Tuple) other;
            return (this.x == that.x) && (this.y == that.y);
        }

        private int x;
        private int y;
    }
}

Note that here we’re using a custom Tuple class which you probably wouldn’t have to implement in the interview or you could just use something like java.awt.Point. The memo here serves as cache for storing in how many ways can we achieve certain sum from certain index. This is not trivial implementation of top down approach. Let’s see if we can do bottom up tabulation approach. Following formula applies:

sum(positive) - sum(negative) = target
sum(positive) + sum(negative) + sum(positive) - sum(negative) = target + sum(positive) + sum(negative)
2 * sum(positive) = target + sum(nums)
sum(positive) = (target + sum(nums)) / 2

Where sum(positive) is the sum of all items chosen with + and sum(negative) sum of all items chosen with -, so we can reframe a problem to find sum(positive) = (target + sum(nums)) / 2, in other words we are only adding positive number and checking in how many ways we can reach the sum(positive). The time and space complexity become O(n*S) where S == sumPositive.

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
        sum += nums[i];
    }
    if(target > sum || (sum + target) % 2 == 1)  return 0;

    int sumPositive = Math.abs((sum + target)) / 2;

    int[][] dp = new int [nums.length+1][sumPositive + 1];

    for(int i = 0; i <= nums.length; ++i){
        dp[i][0] = 1;
    }

    for(int i = 1; i <= nums.length; ++i){
        for(int j = 0; j <= sumPositive; ++j){
            dp[i][j] = dp[i-1][j] + (j >= nums[i-1] ? dp[i-1][j-nums[i-1]] : 0);
        }
    }

    return dp[nums.length][sumPositive];
}

We have a matrix nums.length+1 x sumPositive + 1 and for each dp[i][j] we calculate the number of ways we can reach out the sum j with (or without) the item nums[i]. Can we optimize this further? It turns out we can reduce the space complexity to O(n):

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
        sum += nums[i];
    }
    if(target > sum || (sum + target) % 2 == 1)  return 0;

    int sumPositive = Math.abs((sum + target)) / 2;

    int[] dp = new int [sumPositive + 1];
    dp[0] = 1;

    for(int n : nums){
        for(int j = sumPositive; j >= n; --j){
            dp[j] += dp[j-n];
        }
    }

    return dp[sumPositive];
}

Notice that inner loop starts from sumPositive in other words we iterate from end to start (right to left). In the previous solution we only needed the previous row for calculating the current row, so we can bring down the dimensionality of the matrix and keep only one row. To calculate dp[j] which represents in how many ways we can get sum j if we’re using the current item, we only need to add all the sums calculated in previous iteration which added to n (current element from input array) result in sum j (it’s easy to do that with dp[j-n], number of ways how can get a j-n sum).