Reduction

P = sum of + subset, N = sum of - subset. P - N = target, P + N = sum. → P = (sum + target) / 2. Count subsets with sum P.

Advertisement

Implementation

int findTargetSumWays(int[] nums, int target) {
  int sum = 0;
  for (int n : nums) sum += n;
  if ((sum + target) % 2 != 0 || Math.abs(target) > sum) return 0;
  int P = (sum + target) / 2;
  int[] dp = new int[P + 1];
  dp[0] = 1;
  for (int n : nums)
    for (int s = P; s >= n; s--)
      dp[s] += dp[s - n];
  return dp[P];
}
Advertisement

Edge cases

|target| > sum: 0 ways. (sum + target) odd: 0 ways. All values 0: careful with multiplicity.

Applications

Portfolio balancing (long/short positions). Voting problems.