Target Sum

NeetCode: Target Sum · LeetCode: 494. Target Sum · Difficulty: Medium

Given an integer array nums and an integer target, put a + or - in front of every number. Return the number of sign assignments whose total equals target.

Example

Text

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

Brute force: try both signs for every number

Every number has two choices, so recursion visits 2^n sign assignments, checking the total at the end.

Java

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

    private int dfs(int[] nums, int i, int sum, int target) {
        if (i == nums.length) return sum == target ? 1 : 0;
        return dfs(nums, i + 1, sum + nums[i], target) + dfs(nums, i + 1, sum - nums[i], target);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
        System.out.println(s.findTargetSumWays(new int[]{1}, 2));
        System.out.println(s.findTargetSumWays(new int[]{1}, 1));
    }
}

Output

5
0
1

Time: O(2^n). Space: O(n).

Better: memoise on (index, running sum)

Different sign choices often reach the same running sum at the same index, and the number of completions depends only on (index, sum). Cache those in hash maps. A Java array cannot be a map key (it compares by identity), so the cache is one HashMap<Integer, Integer> per index, keyed by the running sum. The running sum lies in [-total, total], so there are at most n * (2 * total + 1) states.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        List<Map<Integer, Integer>> memo = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) memo.add(new HashMap<>());
        return dfs(nums, 0, 0, target, memo);
    }

    private int dfs(int[] nums, int i, int sum, int target, List<Map<Integer, Integer>> memo) {
        if (i == nums.length) return sum == target ? 1 : 0;
        Integer cached = memo.get(i).get(sum);
        if (cached != null) return cached;
        int ways = dfs(nums, i + 1, sum + nums[i], target, memo)
                 + dfs(nums, i + 1, sum - nums[i], target, memo);
        memo.get(i).put(sum, ways);
        return ways;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
        System.out.println(s.findTargetSumWays(new int[]{1}, 2));
        System.out.println(s.findTargetSumWays(new int[]{1}, 1));
    }
}

Output

5
0
1

Time: O(n · total) where total is the sum of nums. Space: O(n · total).

Optimal: count subsets with a fixed sum

Let P be the numbers given a + and N the numbers given a -. Then sum(P) - sum(N) = target and sum(P) + sum(N) = total. Adding the two gives sum(P) = (total + target) / 2. So the problem becomes: how many subsets of nums sum to (total + target) / 2? That is a 0/1 knapsack counting problem, solved with a single array. The answer is 0 when |target| > total or when total + target is odd (no integer subset sum exists). Once |target| <= total, total + target is not negative, so Java's % (which keeps the sign of the dividend) gives the right parity test. Iterate sums downward so each number is used at most once. Zeros are handled correctly: a 0 can take either sign, and the update dp[0] += dp[0] doubles the count.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
        System.out.println(s.findTargetSumWays(new int[]{1}, 2));
        System.out.println(s.findTargetSumWays(new int[]{1}, 1));
        System.out.println(s.findTargetSumWays(new int[]{0, 0, 1}, 1));
    }
}

Output

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

The reduction requires non-negative numbers, which the problem guarantees. The running time is pseudo-polynomial: it grows with the numeric values, not only the count. LeetCode guarantees the answer fits in a 32-bit int; without that guarantee the counts would need long, because int arithmetic wraps silently on overflow.