Target sum

Put + or - in front of every number so they add up to the target. Count the ways by turning it into a subset-sum count.

The idea

Call the sum of the numbers given + signs P and the sum of the ones given - signs N. Then P - N = target and P + N = total, so P = (total + target) / 2. Every way to sign the numbers is a way to pick a subset that sums to P, so the answer is the number of subsets with sum P: a 1D counting knapsack.

Code

public int FindTargetSumWays(int[] nums, int target) {
    int total = nums.Sum();
    if (Math.Abs(target) > total || (total + target) % 2 != 0)
        return 0; // no split with P - N = target exists
    int p = (total + target) / 2; // P - N = target and P + N = total
    var dp = new int[p + 1];
    dp[0] = 1; // one way to make 0: choose nothing
    foreach (int x in nums)
        for (int s = p; s >= x; s--) // right to left: each number used at most once
            dp[s] += dp[s - x];
    return dp[p];
}

Tips

• If total + target is odd, or |target| > total, P is not a whole number in range, so the answer is 0 straight away. Try target 2 with the default numbers.
• Loop s from high to low so dp[s - x] still holds the count from before x was added; going low to high would let one number be used twice.
• A zero in the input doubles the count (+0 and -0 both work); the same loop handles it because s goes down to x = 0.

In the .NET library

nums.Sum() is LINQ (System.Linq). In a hot loop, a plain foreach total avoids the enumerator, but for interview code Sum() reads best.