Closest Two-Team Split
Problem
Players have skill ratings that are whole numbers, zero or more. Put every player on exactly one of two teams, where a team may end up empty, so that the two team totals are as close as possible. Return the smallest possible difference between the totals.
Examples
Input: ratings = [5, 8, 13, 2]
Output: 2
Why: 13 + 2 = 15 against 5 + 8 = 13; no split reaches 14 eachInput: ratings = [4, 9, 5]
Output: 0
Why: 9 against 4 + 5, a perfect splitInput: ratings = [7]
Output: 7
Why: edge case, one player means one team gets everythingHints
0 / 3
Trying every way to split the players doubles the work with each new player. Look at what actually decides the difference.
Once one team's total is fixed, the difference is fixed too: it is the grand total minus twice that team's total. So the question is which team totals are reachable at all.
Track the set of sums some group of players can reach, starting from just 0. Each player adds a copy of the set shifted by their rating. Then take the reachable sum closest to half the grand total from below.
Solution
A split is decided by one team's total s, and the difference is total minus 2s, so the best split uses the reachable s closest to half the total without passing it. Which sums are reachable is the equal-split question with a different finish: each player either joins the first team or not, so the reachable set after a player is the old set plus the old set shifted by that rating. The set is kept as the bits of one Python integer, where bit s means sum s is reachable, so each player costs one shift and one bitwise or. Time is O(n times the total) bit operations, and space is O(total) bits.
def closest_split(ratings):
total = sum(ratings)
reach = 1 # bit s set: some group sums to s
for r in ratings:
reach |= reach << r # this player joins the group, or not
for s in range(total // 2, -1, -1): # the best team total is at most half
if reach >> s & 1:
return total - 2 * s
print(closest_split([5, 8, 13, 2])) # -> 2
print(closest_split([4, 9, 5])) # -> 0
print(closest_split([7])) # -> 7Stuck on the idea rather than the code? Equal Split covers it.