Challenge: Pick fair football teams
Every Saturday, Tariro organises football on the dusty pitch in Mbare. Last week one team won 9-0 and nobody had fun. This week she has given every player a skill score, and she wants the two teams to be as fair as possible.
The teams do not need the same number of players (the smaller team can have the goalkeeper with the best gloves). What matters is that the total skill of each team is as close as possible.
Your task
Write teamGap(skills). It takes a list of skill scores, one per player, and returns the smallest possible difference between the two teams' totals when every player is put in one team or the other.
teamGap([1, 2, 3, 4]) // 0 1 + 4 = 5 against 2 + 3 = 5
teamGap([7, 3, 2]) // 2 7 against 3 + 2 = 5
teamGap([20, 3, 2]) // 15 20 against 3 + 2 = 5
teamGap([8, 7, 6, 5, 4]) // 0 8 + 7 = 15 against 6 + 5 + 4 = 15
teamGap([]) // 0
Rules
- Every player plays, in exactly one of the two teams.
- A team can have any number of players, even none (useful when there is only one player).
- Skill scores are whole numbers, 0 or more. There are at most 16 players.
- Return the gap as a positive number (or 0).
Tips
- A tempting shortcut is to sort the players and give each one to whichever team is weaker. Try it on
[8, 7, 6, 5, 4]by hand: it gives a gap of 4, not 0. You need to look at more possibilities. - Idea 1, recursion: write a helper
best(i, teamA, teamB)that decides playeri. It tries putting them in team A, then in team B, and returns the smaller gap. Whenireaches the end of the list, the gap isMath.abs(teamA - teamB). - Idea 2, reachable totals: you only need the total of team A, since team B gets the rest. Start with a
Setholding0. For each player, addt + skillfor every totaltalready in the set. At the end, check which total is closest to half of everything. Math.min(...list)andMath.abs(x)are handy here.