Heaviest Plate Subset Within a Barbell Capacity, Up to 42 Plates

You have n barbell plates with weights weights[0], ..., weights[n - 1], and a barbell that can hold a total weight of at most max_capacity. Choose a subset of the plates, using each plate at most once, whose total weight is as large as possible without exceeding max_capacity. Return that maximum total weight.

Function Signature

def max_lift(weights: list[int], max_capacity: int) -> int:

Rules

• The empty subset is allowed, so the answer is 0 when every plate is heavier than max_capacity.
• Plates with equal weights are distinct plates, and each one may be used at most once.
• Return only the maximum total weight, not the chosen plates.

Constraints

• 1 <= n <= 42, where n = len(weights)
• 1 <= max_capacity <= 10^9
• 1 <= weights[i] <= 10^9
• The total of all weights can reach 4.2 * 10^10, which exceeds 2^31 - 1, so use 64-bit integers for sums. All sums stay far below 2^53.

Examples

Example 1

Input:  weights = [7, 1, 5, 6, 2], max_capacity = 7
Output: 7

For example, the plate of weight 7 alone, or the plates 1 and 6, or 5 and 2, reach the capacity exactly.

Example 2

Input:  weights = [4, 8, 9], max_capacity = 16
Output: 13

The plates 8 and 9 total 17, which is too heavy. The best feasible subset is 4 and 9.

Example 3

Input:  weights = [10, 20, 30], max_capacity = 5
Output: 0

Every plate exceeds the capacity, so only the empty subset fits.

Heaviest Barbell Load Within Capacity

Hints

1. n is at most 42 while the weights and the capacity reach 10^9: let the small bound on the number of plates, not the size of the numbers, drive your approach.
2. Every plate is positive, so once a partial selection is heavier than max_capacity, adding more plates can never make it feasible again.
3. Sums of only a few plates can exceed 2^31 - 1, so keep every total in a 64-bit integer.

Approach

Meet in the middle. If the total of all plates fits, return it directly. Otherwise split the plates by position into two halves of at most 21 plates each and list every subset sum of each half that does not exceed max_capacity. Because every plate is positive, a partial sum above the capacity can never become feasible again, so such sums (and any single plate heavier than the capacity) are dropped without losing an answer. Sort the distinct sums of the second half. For each first-half sum s, binary-search the largest second-half sum that is at most max_capacity - s; it always exists because the empty subset contributes 0. Every subset of all plates is exactly one pair (subset of the first half, subset of the second half), and the pair is feasible exactly when the two sums add to at most max_capacity, so the maximum of s plus its best partner over all s is the answer. The search stops early once that maximum equals max_capacity, since nothing can exceed it. Edge cases: n = 1 (the first half is empty and contributes only 0), every plate heavier than the capacity (only the empty subset remains, answer 0), duplicate weights (subsets are enumerated by position, so each plate is used at most once), and totals above 2^31 - 1 (all arithmetic is 64-bit; in JavaScript every sum stays below 2^53).

• Time complexity: O(2^(n/2) * n)
• Space complexity: O(2^(n/2))