You're packing trail mix from snack packets; packets[i] = (protein_i, sugar_i) grams. Take each packet at most once, and hit exactly protein grams of protein and exactly sugar grams of sugar.
Write count_mixes(packets: list[tuple[int, int]], protein: int, sugar: int) -> int: how many subsets (by position, so identical packets count separately) hit both targets. The empty subset counts when both are 0.
count_mixes([(3, 1), (2, 2), (1, 1), (4, 2)], 5, 3) # 2 ((3,1)+(2,2) and (4,2)+(1,1))
count_mixes([(1, 1), (1, 1)], 1, 1) # 2 (either packet)
count_mixes([(5, 5)], 0, 0) # 1 (take nothing)
count_mixes([(2, 3)], 2, 4) # 0
Up to 34 packets; all gram values up to 10^9, so a DP over sums won't fit.
⭐ Bonus: trying all 2^n subsets still passes the smaller tests; the speed tests with 34 packets earn a star at about 2^(n/2) work (split the packets in half).
Show hint
a mix is some packets from the first half plus some from the second (at most 2^17 subsets each). Count one half's (protein, sugar) totals in a dict, then look up the partner each subset of the other half needs.