Subset Sum Counting

Count ways to reach each sum with DP over items; bitset convolution counts subset sums in XOR/AND semantics for 0/1 knapsack style.

Try this in Python

# Count subsets with sum == target (0/1 items, toy)
items = [1, 2, 3]
target = 3

def count_subsets() -> int:
    dp = [0] * (target + 1)
    dp[0] = 1
    for x in items:
        for s in range(target, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[target]


print(count_subsets())

Key takeaways

• Iterate sums backwards when each item used once.
• Bitset dp shifts OR-combine for huge sum bounds—space trick.
• Separate counting from existence.