sum-over-subsets.md

Sum over subsets

Code

for (auto i=0; i<(1<<n); ++i)
	dyn[i] = xs[i];
for (auto i=0; i<n; ++i)
	for (auto mask=0; mask<(1<<n); ++mask)
		if (mask & (1 << i))
			dyn[mask] += dyn[mask ^ (1 << i)];

Problems

• Special Pairs
• Compatible Numbers
• Vowels
• Covering Sets
• COCI 2011/2012 Problem KOSARE
• Vim War
• Jzzhu and Numbers
• Subset
• Jersey Number
• Beautiful Sandwich
• Pepsi Cola (join group)
• Uchiha and Two Products
• Strange Functions
• Varying Kibibits
• Snake Escaping (JOI 2018)

Sources

• https://codeforces.com/blog/entry/45223
• https://www.geeksforgeeks.org/sum-subsets-dynamic-programming/