Subset Sums — Exact Count

Challenge on lesson: Checkpoint — Attack Patterns

CHALLENGE

Difficulty: advanced+25 XP

**Bài toán.** Given n items with weights w[i] and a target S, count the subsets whose weights sum exactly to S. **Constraints:** 1 ≤ n ≤ 30; |w[i]| ≤ 10^9; |S| ≤ 10^12. **Output:** the count. An enumeration of all 2^n subsets will NOT fit the time limit; meet-in-the-middle will.

Press Submit to check your solution.

Back to lesson: Checkpoint — Attack Patterns