Most packages of at most two items with equal total cost

You have items with costs item_costs. Make as many packages as you can, where each package holds one or two items, every package has the same total cost, and no item is used twice. You choose the common total. Return the largest number of packages.

Interface

Unless you agree on a different interface with the interviewer, assume:

• max_packages(item_costs: list[int]) -> int — 0 for an empty list.

Example

[1, 2, 3, 4]           ->  2   # total 5: (1,4) and (2,3)
[2, 2, 2, 2]           ->  4   # total 2: four single items beat two pairs at 4
[3, 1, 4, 2, 5, 5]     ->  4   # total 5: (5), (5), (1,4), (3,2)
[6, 1, 5, 3, 3, 6, 2]  ->  4   # total 6: (6), (6), (1,5), (3,3)

Constraints

• 0 <= len(item_costs) <= 10^4, 0 <= item_costs[i] <= 10^9.

Clarifying questions

• May a package hold a single item, or must it hold exactly two?
• Can costs be zero, and does a zero-cost item count as a package on its own?
• Do I return the count only, or the packages too?

What a strong answer covers

• The common total must be some item's cost or the sum of two items' costs, so those are the only candidates: O(n^2) of them in the worst case, far fewer distinct ones when values repeat.
• For a fixed total S, using every item that costs S as its own package is never worse than pairing it; the rest pair value a with S - a, min(count[a], count[S - a]) times, and count[a] // 2 when a == S - a.
• Doing it in one sweep instead of per candidate: over every pair of distinct positive values a < b, add min(count[a], count[b]) to total[a + b], and count[a] // 2 to total[2a]; then add the singles count[S] to each total. Zeros never go into pairs, since an item alone is as good as that item plus a zero. That is O(D^2) for D distinct values, with a frequency map.
• Tests: an empty list, all equal costs, a single item, zeros.

Follow-ups

• Packages must hold exactly two items.
• Packages may hold up to three items.
• Return the packages themselves.