Target Sum

medium array dp backtracking

Problem

You are given an integer array nums and an integer target. Build expressions by adding '+' or '−' in front of each integer. Return the number of expressions that evaluate to target.

Inputnums = [1, 1, 1, 1, 1], target = 3

Output5

Let P = sum of '+' subset. Then 2·P − total = target, so P = (target + total)/2. Count subsets summing to P.

nums

target

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (target + total) % 2 or abs(target) > total: return 0
    p = (target + total) // 2
    dp = [0] * (p + 1)
    dp[0] = 1
    for x in nums:
        for s in range(p, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[p]

function findTargetSumWays(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  if ((target + total) % 2 !== 0 || Math.abs(target) > total) return 0;
  const p = (target + total) / 2;
  const dp = new Array(p + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    for (let s = p; s >= x; s--) dp[s] += dp[s - x];
  }
  return dp[p];
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0; for (int x : nums) total += x;
        if (((target + total) & 1) != 0 || Math.abs(target) > total) return 0;
        int p = (target + total) / 2;
        int[] dp = new int[p + 1];
        dp[0] = 1;
        for (int x : nums)
            for (int s = p; s >= x; s--) dp[s] += dp[s - x];
        return dp[p];
    }
}

int findTargetSumWays(vector<int>& nums, int target) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (((target + total) & 1) || abs(target) > total) return 0;
    int p = (target + total) / 2;
    vector<int> dp(p + 1, 0);
    dp[0] = 1;
    for (int x : nums)
        for (int s = p; s >= x; s--) dp[s] += dp[s - x];
    return dp[p];
}

Explanation

Instead of trying every +/- assignment (which would be exponential), we turn this into a subset-counting problem. Split the numbers into a positive group P (gets a +) and a negative group N (gets a -).

Since P - N = target and P + N = total, a little algebra gives P = (target + total) / 2. So we just need to count how many subsets sum to P. If (target + total) is odd or target is too big, no answer exists and we return 0.

We solve the subset count with a 0/1 knapsack DP. dp[sum] holds the number of subsets that add up to sum. We start with dp[0] = 1 (the empty subset) and for each number x we sweep s downward doing dp[s] += dp[s - x].

The backward sweep matters: it stops us from using the same x twice in one subset, keeping it a true 0/1 choice.

Example: nums = [1,1,1,1,1], target = 3. Here total = 5, so P = (3 + 5)/2 = 4. The number of ways to pick five 1's that add to 4 is dp[4] = 5, which is the answer.

Time: O(n · P) where P = (target + total)/2 Space: O(P)