Subset sum

Decide whether any subset of an array sums to a given target. The general table-building behind many knapsack-style problems.

The idea

dp[i, t] asks whether sum t is reachable using only the first i numbers. It is reachable either by ignoring number i (dp[i-1, t]) or, if it fits, by using number i and reaching the remaining amount with the earlier numbers (dp[i-1, t - a[i-1]]).

Code

public static bool SubsetSum(int[] a, int target) {
    var dp = new bool[a.Length + 1, target + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = true;
    for (int i = 1; i <= a.Length; i++)
        for (int t = 1; t <= target; t++)
            dp[i, t] = dp[i - 1, t] || (a[i - 1] <= t && dp[i - 1, t - a[i - 1]]);
    return dp[a.Length, target];
}

Tips

• Column 0 is always true: an empty subset already sums to 0.
• This whole table only needs the row above it, so it can be compressed to a single array filled right to left.

In the .NET library

This is the same table shape as 0/1 knapsack and partition equal subset sum, just asking a yes/no question about one explicit target instead of maximising value or forcing an exact half.