Subset sum counting

Count ways — item DP; bitset convolution.

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

• 0/1 — backward sum loop.
• Bitset space trick.
• Count vs exists.