Minimum Difference Partition

You are given a set of weights. Your task is to divide these weights into two groups such that the absolute difference between the sum of weights in the two groups is minimized.

Let \(S_1\) and \(S_2\) be the sums of the two groups. Note that \(S_1 + S_2 = S\), where \(S\) is the total sum of all weights. The goal is to minimize \(|S_1 - S_2|\). This problem can be efficiently solved using dynamic programming.

inputFormat

The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains an integer \(k\) indicating the number of weights. The following line contains \(k\) space-separated integers representing the weights.

outputFormat

For each test case, output a single line containing the minimum possible absolute difference between the sums of the two groups.

2
4
1 3 5 7
3
10 20 30

0
0