494. Target Sum

Time: O(n*sum)

Space: O(n*sum)

Intuition

Assign + or - to each number. DP: count ways to reach each possible sum. Or reduce to subset sum: let P = positive subset. P - (total-P) = target → P = (total+target)/2.

Algorithm

1If (total+target) is odd or |target| > total, return 0.
2Find count of subsets summing to (total+target)/2.
3Use 1D DP: dp[j] = number of ways to reach sum j.
4For each num: iterate j from target down to num: dp[j] += dp[j-num].

Example Walkthrough

Input: nums=[1,1,1,1,1], target=3

1.total=5, need sum=4.
2.Ways to choose 4 from [1,1,1,1,1] = C(5,4) = 5.

Output: 5

Common Pitfalls

•dp[0]=1 (empty subset). Check (total+target)%2 == 0 before proceeding.

494.cs

// Approach: Reduce to subset sum: assign '+' to a subset summing to
// (total + target)/2. Top-down DP with memoization counts the ways.
// Time: O(n*sum) Space: O(n*sum)

public class Solution
{
    public int FindTargetSumWays(int[] nums, int target)
    {
        int n = nums.Length;
        int totalSum = 0;
        for (int i = 0; i < n; i++)
            totalSum += nums[i];

        int remaining = totalSum - target;

        if (remaining < 0 || remaining % 2 > 0)
            return 0;
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++)
        {
            int[] arr = new int[(remaining / 2) + 1];
            Array.Fill(arr, -1);
            dp[i] = arr;
        }
        return topDown(n - 1, remaining / 2, nums, dp);
    }

    private static int topDown(int ind, int target, int[] arr, int[][] dp)
    {
        if (ind == 0)
        {
            if (target == 0 && arr[ind] == 0)
                return 2;

            if (target == 0 || arr[ind] == target)
                return 1;

            return 0;
        }

        if (dp[ind][target] != -1)
            return dp[ind][target];

        int notTake = topDown(ind - 1, target, arr, dp);
        int take = 0;
        if (arr[ind] <= target)
            take = topDown(ind - 1, target - arr[ind], arr, dp);

        int ans = take + notTake;
        dp[ind][target] = ans;
        return ans;
    }
}

Was this solution helpful?