Given array nums and target, assign + or - to each number. Find the number of ways to make the expression equal to target.
Input: nums=[1,1,1,1,1], target=3 → Output: 5Input: nums=[1], target=1 → Output: 1
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).
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