Target Sum

Problem

Prepend +/- to each value in nums so the total equals target. Return the number of ways.

Constraints

• 1 ≤ n ≤ 20
• 0 ≤ nums[i] ≤ 1000

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def findTargetSumWays(self, nums, target):
        from collections import defaultdict
        dp = defaultdict(int)
        dp[0] = 1
        for x in nums:
            nxt = defaultdict(int)
            for s, c in dp.items():
                nxt[s + x] += c
                nxt[s - x] += c
            dp = nxt
        return dp[target]

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.