Introduction

The distinct subset-sum problem asks how many different totals can be formed by summing arbitrary subsets of a given set or list of numbers. It appears in combinatorics and dynamic programming, and it is a good example of a problem where the number of subsets can be enormous even though the number of reachable sums may still be manageable.

Start With A Small Example

For the values [1, 2, 3], the subset sums are:

1{} -> 0
2{1} -> 1
3{2} -> 2
4{3} -> 3
5{1, 2} -> 3
6{1, 3} -> 4
7{2, 3} -> 5
8{1, 2, 3} -> 6

The distinct totals are:

0, 1, 2, 3, 4, 5, 6

There are 8 subsets but only 7 distinct sums because both {3} and {1, 2} produce 3.

Incremental Dynamic Programming

The cleanest general approach is to build the set of reachable sums incrementally. Start with {0} for the empty subset. When you process a value x, every currently reachable sum s creates a new reachable sum s + x.

That leads to a compact Python solution:

1def count_distinct_subset_sums(values):
2    reachable = {0}
3
4    for x in values:
5        reachable |= {s + x for s in reachable}
6
7    return len(reachable), reachable
8
9count, sums = count_distinct_subset_sums([1, 2, 3])
10print(count)
11print(sorted(sums))

This is dynamic programming because it reuses previously computed reachable sums instead of enumerating every subset explicitly. It is simple, correct, and usually the best starting point.

Boolean DP When Values Are Nonnegative

If all values are nonnegative and the total sum is not too large, a boolean table is often faster and more memory-predictable:

1def count_distinct_subset_sums_dp(values):
2    total = sum(values)
3    possible = [False] * (total + 1)
4    possible[0] = True
5
6    for x in values:
7        for s in range(total - x, -1, -1):
8            if possible[s]:
9                possible[s + x] = True
10
11    return sum(possible)
12
13print(count_distinct_subset_sums_dp([1, 2, 3]))

The reverse iteration is crucial. If you loop forward, a value can be reused more than once during the same step, which turns the algorithm into something closer to an unbounded knapsack.

Bitset Optimization

A compact optimization for nonnegative integers is to treat reachability as bits in an integer:

1def count_distinct_subset_sums_bitset(values):
2    bits = 1  # bit 0 is reachable
3    for x in values:
4        bits |= bits << x
5    return bits.bit_count()
6
7print(count_distinct_subset_sums_bitset([1, 2, 3]))

Shifting left by x means "add x to every currently reachable sum." The bitwise OR merges old sums and new sums. This trick is elegant and often very fast in languages with efficient bit operations.

The Answer Is Not Determined By 2^n

It is easy to assume the answer is either close to 2^n or close to the total sum, but neither is reliable. A few examples show why:

• '[1, 1, 1] gives sums 0, 1, 2, 3, so the answer is 4'
• '[2, 4] gives sums 0, 2, 4, 6, so the answer is 4'
• '[1, 3] gives sums 0, 1, 3, 4, so the answer is also 4'

Different value patterns can collapse many subsets onto the same total. That is why the distinct-sum count depends on the structure of the input, not just its size.

Generating-Function View

Mathematically, you can also write the problem as the polynomial:

(1 + x^a1)(1 + x^a2)...(1 + x^an)

The exponent s appears with a nonzero coefficient if and only if some subset sums to s. That viewpoint is elegant and useful in proofs, though for actual implementation the set-based and bitset dynamic programs are usually more practical.

What About Negative Numbers

Negative values make the problem slightly less convenient because the simple boolean-array approach assumes sums start at 0 and move upward. The set-based method still works:

print(count_distinct_subset_sums([-2, 3, 5]))

That flexibility is one reason the set-based approach is a good default unless you know the input is nonnegative and performance matters enough to justify a specialized representation.

Common Pitfalls

• Enumerating all 2^n subsets directly when dynamic programming would be far more efficient.
• Forgetting that distinct subsets can produce the same total.
• Updating a boolean DP array forward and accidentally reusing the same item multiple times.
• Using bitset or array-based tricks without confirming the input is nonnegative.
• Assuming the number of distinct sums is determined only by n instead of by the input values.

Summary

• Distinct subset sums count unique reachable totals, not subsets.
• A set-based incremental DP is the simplest general-purpose solution.
• A boolean DP array is efficient when values are nonnegative and the total sum is moderate.
• A bitset implementation is a compact optimization for nonnegative integers.
• Input structure matters: many different subsets can collapse to the same sum.