Minimum Sum Partitioning

★★★★★

4.8

4 votes

Hard

Details

Submissions

Discussion

Editorial

Problem

You are given an array of size $n$ . Your task is to divide the array into two sets, such that the absolute difference between their sums is minimum possible.

You will have to answer $q$ independent queries.

INPUT:

The first line contains an integer $q$ , the number of queries.

The next lines contain $q$ queries. For each query, the first line contains an integer $n$ , the size of the array. The second line contains $n$ integers, the numbers in the array.

OUTPUT:

For each query, print the minimum absolute difference in a new line.

CONSTRAINTS:

${1 \le q \le 30}$

${1 \le n \le 50}$

${1 \le a[i] \le 50}$

Sample Input

Sample Output

1
23

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first query, an optimal partition would be ${\{1, 5, 6\}}$ and ${ \{ 11 \} }$ , so the answer would be $(1+5+6)-(11) = 1$ .