Solution 3: Dynamic programming

Finally, we turn to the dynamic programming solutions.

As with all dynamic programming solutions, we solve for the base case first, and reuse our previous solutions to smaller sub-problems to solve larger ones.

Our base case: when we have no values to add/subtract, we have a sum of 0, and therefore there is only one way to arrive at S = 0.

The key idea in this dynamic programming solution is to only branch out from reachable target sums.

At the first iteration (i.e. the outer for-loop), assume that we are on value x in our nums array. Therefore, we know intuitively that there is only one way to reach the target sum of +x and -x. (Explanation: you start with 0, and you either +x or -x.) Programmatically, we can express this logic by setting ways to reach x = ways to reach 0 and ways to reach -x = ways to reach 0.

In subsequent iterations, we only care about starting from target sums that are already reachable. Assume that the second value is y. We know intuitively that after 2 iterations, we can only arrive at 4 possible target sums: x + y, x --- y, -x + y, and-x --- y. Note: These 4 values may not be distinct!

xxxxxxxxxx

}

class Main {

    public static int findTargetSumWays(int[] nums, int S) {

        int sum = 0;

        for (int num: nums) sum += num;

        if (S > sum || -S < -sum) return 0;

​

        int[] dp = new int[2 * sum + 1];

        dp[sum] = 1;

​

        for (int num: nums) {

            int[] next = new int[2 * sum + 1];

            for (int i = 0; i < dp.length; i++) {

                // Only branch out from reachable target sums\

                if (dp[i] == 0) continue; next[i + num] += dp[i];

                next[i - num] += dp[i];

            }

            dp = next;

        }

​

        return dp[sum + S];

    }

​

    public static void main(String[] args) {

        int[] nums = {

            8,

            7,

            1,

            5,

            3,