All problems

Fair Relay Teams

Medium · dynamic programming

A swimming club is entering a relay gala with two teams. The list times holds the best lap time, in seconds, of each of the club's swimmers. The number of swimmers is even.

Split the swimmers into two teams with exactly the same number of swimmers each. A team's total is the sum of the lap times of its members. Every swimmer joins exactly one team.

The coach wants the race to be as close as possible. Return the smallest possible difference between the two team totals (always a number that is 0 or more).

Examples

Example 1

Input: times = [3, 1, 4, 2]

Output: 0

Putting the swimmers with times 3 and 2 in one team and 1 and 4 in the other gives totals 5 and 5.

Example 2

Input: times = [10, 1, 1, 1]

Output: 9

Whoever joins the 10 makes a team of 11 against a team of 2.

Example 3

Input: times = [6, 6]

Output: 0

Each team is a single swimmer.

Constraints