Subset Masks and SOS-Style DP

DP over subsets often iterates mask from 0..2^n-1; combine with SOS DP when you need sums over supersets or subsets quickly.

Why this shows up in the real world

Team formation under compatibility bitmask. Circuit signal subsets.

Core idea (explained for students)

For n<=20 brute force masks; above that look for meet-in-the-middle or greedy proofs.

Try this in Python

def count_subset_sums(nums: list[int], target: int) -> int:
    from itertools import combinations

    n = len(nums)
    c = 0
    for r in range(n + 1):
        for comb in combinations(range(n), r):
            if sum(nums[i] for i in comb) == target:
                c += 1
    return c


print(count_subset_sums([1, 2, 3, 4, 5], 10))

Common mistakes

• Iterating subsets of mask incorrectly—use sub = mask; while sub: sub=(sub-1)&mask pattern.
• Integer vs bit length confusion.

Key takeaways

• Precompute popcount if transitions depend on it.