650. Tug of War
A coach has an even number of players, and nums[i] is the strength of player i; strengths may be negative for players who pull the wrong way. Split the players into two teams with exactly the same number of players, using every player once. The gap of a split is the absolute difference between the total strengths of the two teams.
Return the smallest gap over all splits into two equally sized teams.
Example 1
- Input:
- nums = [1,5,2,6]
- Output:
- 0
- Explanation:
Put 1 and 6 in one team and 5 and 2 in the other: 7 against 7, a gap of 0.
Example 2
- Input:
- nums = [4,1]
- Output:
- 3
- Explanation:
Each team has one player, so the gap is |4 - 1| = 3.
Example 3
- Input:
- nums = [-3,7,2,-8]
- Output:
- 0
- Explanation:
Team (7, -8) has strength -1 and team (-3, 2) also has -1, so the gap is 0.
Constraints
nums.lengthis even and 2 ≤nums.length≤ 30- -106 ≤
nums[i]≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(2^(n/2) * n)
- Space
- O(2^(n/2))