Tug of War Partition Problem

The task is to partition a group of people into two teams such that the absolute difference between the sum of their strengths is minimized. You are given an integer (n) denoting the number of people, along with (n) integers representing each person’s strength. Your goal is to assign each person to one of the two teams so that the difference between the total strengths of the teams is as small as possible.

One common approach is to use dynamic programming similar to the subset-sum problem in which you try to get as close as possible to (\frac{\text{total strength}}{2}).

inputFormat

The input is provided via standard input (stdin) and is structured as follows:
1. The first line contains an integer (n) ((1 \leq n \leq 1000)) which denotes the number of people.
2. The second line contains (n) space-separated integers, each representing the strength of a person.

outputFormat

Output a single integer to standard output (stdout), which is the minimum possible absolute difference between the sum of the strengths of the two teams.## sample

4
1 6 5 11

1