Minimum Subset Sum Difference Partitioning

You are given a list of n integers. Your task is to partition the list into two subsets such that the absolute difference between the sums of the two subsets is minimized.

Let \(S\) be the total sum of the array. Then the problem can be formulated as finding a subset with sum \(s\) (where \(0 \leq s \leq S/2\)) such that \(s\) is as large as possible and the resulting difference \(|(S - s) - s|\) is minimized.

For example, for the array [1, 2, 3, 9], one optimal partition is [1, 2, 3] and [9]. The difference is \(|6 - 9| = 3\). This problem requires you to compute that minimum difference.

inputFormat

The first line of the input contains an integer \(T\) representing the number of test cases. For each test case:

1. The first line contains an integer \(n\) indicating the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing an integer which is the minimum absolute difference between the sums of the two subsets.

1
4
1 2 3 9

3