Dynamic Programming • 0/1 Knapsack

Target Sum

You are given an integer array and a target integer. Assign '+' or '-' to each integer so that the sum evaluates to the target. Return the number of different ways to do this.

Try Interactive Simulator

Overview

This looks like a Backtracking problem at first. However, we can use a math trick to convert it into a pure DP subset counting problem.

The Math Trick

Let `P` be the sum of positive numbers, and `N` be the sum of negative numbers. We know `P - N = Target` and `P + N = TotalSum`. Solving for `P` gives: `P = (Target + TotalSum) / 2`.

Subset Counting

The problem is completely reduced to: "Find the number of subsets whose sum is exactly `P`". This is standard 0/1 Knapsack.

Edge Cases

If `Target + TotalSum` is odd, or if `abs(Target) > TotalSum`, it's mathematically impossible to reach the target, so we return `0` immediately.

1

DP Array (Number of Ways to Reach Sum j)

0

1

0

2

0

3

0

4

0

Code Tracker

:::

1let sum = nums.reduce((a, b) => a + b, 0);

2if (Math.abs(S) > sum || (sum + S) % 2 !== 0) return 0;

3let target = (sum + S) / 2;

4let dp = new Array(target + 1).fill(0);

5dp[0] = 1;

6for (let i = 0; i < nums.length; i++) {

7 for (let j = target; j >= nums[i]; j--) {

8 dp[j] += dp[j - nums[i]];

9 }

10}

11return dp[target];