Target Sum

Given array nums and target, assign + or - to each number. Find the number of ways to make the expression equal to target.

Example 1

Input: nums=[1,1,1,1,1], target=3 → Output: 5

Example 2

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

Solution Approach

DP with offset: define dp[i][sum+offset] = ways to reach sum using first i numbers. Use a HashMap for sparse state representation.

Use HashMap where key=running_sum, value=ways_to_reach.
Initialize {0: 1}.
For each num: new map with +num and -num from each existing state.
Return map.getOrDefault(target, 0).

Java

import java.util.*;

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> e : dp.entrySet()) {
                next.merge(e.getKey() + num, e.getValue(), Integer::sum);
                next.merge(e.getKey() - num, e.getValue(), Integer::sum);
            }
            dp = next;
        }
        return dp.getOrDefault(target, 0);
    }
}

Time Complexity: O(N * sum)
Space Complexity: O(sum). HashMap