# The one idea Partitioning defeats every state you have met so far: which values remain matters, not how many or their sum — `{4, 6}` left over is a different world from `{8, 2}`. When $n \le 17$, stop compressing and make the state **the set itself**, encoded as a bitmask: `dp[mask]` = best way to pack exactly the values in `mask`. That is $2^{17} = 131072$ states — small — and the fill order is just increasing mask value, because adding an element only ever sets a bit (a subset's integer value is always smaller than its superset's). "Best" needs care: two packings of the same set can differ in *group count* and in *room left in the open group*, and fewer groups does not always win the future — a packing with equal groups but a fuller open group might. The reference orders lexicographically: minimize groups first, then the open group's load, packed into one integer: ```python BIG = limit + 1 dp[mask] = groups * BIG + load # load < BIG, so this order is lexicographic ``` ```python dp = [INF] * (1 << n) dp[0] = BIG # one open, empty group for mask in range(1 << n): load = dp[mask] % BIG base = dp[mask] - load for i in range(n): if mask & (1 << i): continue v = values[i] cand = base + load + v if load + v <= limit else base + BIG + v dp[mask | 1 << i] = min(dp[mask | 1 << i], cand) return dp[-1] // BIG ``` Each element joins the current open group if it fits, or closes it and opens a new one. Is greedy-within-the-mask safe — must the *minimum* packed value be optimal? The subtlety: (fewer groups, fuller open group) always dominates (fewer groups, emptier) — same prefix freedom, more used — and strictly fewer groups can afford any load the extra group could have absorbed. Minimizing the packed integer therefore keeps, for every mask, a packing that some optimal completion extends. This dominance argument is what you must re-prove any time you borrow the trick. ## Where bitmask DP lives The technique is the last resort *before* brute force: $2^n \cdot n$ beats $n!$ orderings precisely because packings that use the same set — in any order — collapse into one state. Same collapse as every DP category, applied to a state nothing smaller can express. TSP ("shortest tour visiting all cities") is the canonical citizen; $n \le 20$ in a constraint is the neon sign. ## Cost $O(2^n \cdot n)$ time, $O(2^n)$ space — about 2.2M transitions at $n = 17$, which is also Python's practical ceiling for this shape (the 3-second limit here is doing work). At $n = 25$ no language survives; bitmask constraints are non-negotiable. ## Check yourself `dp[0] = BIG` claims one *empty open group* already exists — group count 1, load 0. Why must the empty packing start at one group, not zero? Trace `values = [5]`, `limit = 10` through both conventions and watch the off-by-one appear.

Problems1

Problems1