Bool DP

boolean subsetSum(int[] nums, int S) {
  boolean[] dp = new boolean[S + 1];
  dp[0] = true;
  for (int num : nums)
    for (int s = S; s >= num; s--)
      dp[s] |= dp[s - num];
  return dp[S];
}
Advertisement

Count subsets

int[] dp = new int[S + 1];
dp[0] = 1;
for (int num : nums)
  for (int s = S; s >= num; s--)
    dp[s] += dp[s - num];
// dp[S] = number of subsets summing to S
Advertisement

NP-hard general, pseudopolynomial DP

Complexity O(N × S) is pseudopolynomial (depends on target value). Still fast for moderate S.

Applications

Partition problems. Cryptography (subset-sum ciphers). Combinatorial enumeration.