Closest Two-Team Totals
Medium2-D Dynamic Programming
Problem
A coach splits players with strength ratings strengths into two teams. Every player must join exactly one team, and a team may be empty.
Return the smallest possible absolute difference between the two teams' total strengths.
Example 1
- Input:
- strengths = [8, 3, 6, 4]
- Output:
- 1
Teams {8, 3} = 11 and {6, 4} = 10 differ by 1; an even split of 21 is impossible.
Example 2
- Input:
- strengths = [5, 9, 2]
- Output:
- 2
{9} against {5, 2}.
Constraints
- 1 ≤ strengths.length ≤ 30
- 1 ≤ strengths[i] ≤ 100
Hint
Show the first hint
If one team totals s, the other totals total - s. What is the difference as a function of s?
Walkthrough
How to approach it
01Clarify before coding
- Can a team be empty? Yes, so a single player gives a difference equal to their strength.
- Do teams need equal headcounts? No, only totals matter.
- Is the answer unique? The minimum value is; several splits may achieve it, but we only return the number.
02Brute force
Assign each player to team A or team B in all 2^n ways and track the smallest |A - B|.
Cost: O(2^n · n): about 3 · 10^10 operations for n = 30.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.