Tug of War

You are given a list of participants' strengths represented as integers. Your task is to divide these participants into two teams such that the absolute difference between the total strengths of the teams is minimized.

Formally, let the strengths be \(a_1, a_2, \dots, a_n\). Let \(S_1\) and \(S_2\) be the sums of the strengths for the two teams. You need to partition the list so as to minimize \(|S_1 - S_2|\).

The input is given via standard input, where the first line contains an integer \(n\) representing the number of participants, and the second line contains \(n\) space-separated integers representing the strengths. Output the minimum possible difference between the total strengths of the two teams.

Example:
Input: 4 followed by 3 1 4 2
Output: 0 (since the teams can be split as [3,1] and [4,2], which both sum to 4)

inputFormat

The first line of input contains an integer \(n\) (\(2 \leq n \leq 1000\)) — the number of participants. The second line contains \(n\) integers, where each integer represents the strength of a participant. These integers are space-separated.

outputFormat

Output a single integer — the minimum absolute difference between the total strengths of the two teams.

4
3 1 4 2

0