Minimum Subset Difference

Problem Statement: Given an array of positive integers, partition the array into two non-empty subsequences such that the absolute difference between the sums of the two subsequences is minimized. Formally, let the array be \(A = [a_1, a_2, \dots, a_n]\) and let \(S\) be a non-empty proper subset of \(A\) (i.e. \(S \neq \emptyset\) and \(S \neq A\)). The task is to determine the minimum value of \(|\text{sum}(S) - (\text{total sum} - \text{sum}(S))|\).

Input Constraints:

• \(1 \leq n \leq 1000\), where \(n\) is the number of elements in the array.
• Each element in the array is a positive integer.

Explanation: You are required to use dynamic programming to determine all possible subset sums and then find the one which minimizes the difference from the total sum. The answer for each test case should be output on a new line.

inputFormat

The input begins with an integer T, the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer n denoting the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

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

3
4
1 6 11 5
3
10 20 15
5
3 1 4 2 2

1
5
0