Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Medium

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`.

Examples

Input:nums = [1,1,1,1,1], target = 3
Output:5
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
Input:nums = [1], target = 1
Output:1
There is only one way to reach the target: +1

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Dynamic Programming (Memoization)

Approach

We can use recursion with memoization. At each index `i`, we have two choices for `nums[i]`: add it or subtract it. Our state is `(index, current_sum)`. We recursively calculate the number of ways to reach the `target` from this state. To avoid recalculating the same subproblems, we cache the results in a hash map where the key is a string or object representing `(index, current_sum)`.

Complexity Analysis

Time Complexity
O(n * totalSum)
Space Complexity
O(n * totalSum)

The number of possible states is bounded by the length of the array `n` and the range of possible sums (from `-totalSum` to `totalSum`). Both time and space complexities are proportional to the number of unique states.

Solution.java
class Solution {    public int findTargetSumWays(int[] nums, int target) {        // Map to store (index + "," + currentSum) -> count        Map<String, Integer> memo = new HashMap<>();        return backtrack(nums, target, 0, 0, memo);    }        private int backtrack(int[] nums, int target, int index, int currentSum, Map<String, Integer> memo) {        if (index == nums.length) {            return currentSum == target ? 1 : 0;        }                String key = index + "," + currentSum;        if (memo.containsKey(key)) {            return memo.get(key);        }                // Choice 1: Add the current number        int add = backtrack(nums, target, index + 1, currentSum + nums[index], memo);        // Choice 2: Subtract the current number        int subtract = backtrack(nums, target, index + 1, currentSum - nums[index], memo);                memo.put(key, add + subtract);        return add + subtract;    }}