You're packing trail mix for a long hike from a shelf of snack packets. Packet i holds packets[i] = (protein_i, sugar_i) grams. You may take each packet at most once, and the bag must contain exactly protein grams of protein and exactly sugar grams of sugar.
Write count_mixes(packets: list[tuple[int, int]], protein: int, sugar: int) -> int returning how many subsets of the packets (chosen by position, so identical packets count separately) hit both targets. The empty subset counts when both targets 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
Constraints: 0 <= len(packets) <= 34, 0 <= protein_i, sugar_i, protein, sugar <= 10^9.
Gram counts go up to 10^9, so a DP over sums is out, and 2^34 subsets is too many to list. Aim for about 2^(n/2) work (times a log factor at most).
Show hint
A mix is some packets from the first half of the list plus some from the second half; each half has at most 2^17 subsets. Count the (protein, sugar) totals of one half's subsets in a dictionary, then look up the partner each subset of the other half needs.