Minimum Difference

Time Limit: 3 sec

 

The Problem

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of first subset must be (n-1)/2 and size of second subset must be (n+1)/2.

 

Example:

Let given set be {23, 45, 34, 12, 0, 3, 1, 4}, the size of set is 8.

Subsets for this set should be {45, 12, 3, 1} and {23, 34, 0, 4}.

Both output subsets are of size 4 and sum of elements in both subsets is same (61 and 61).

The minimum difference of the sum of two subsets 0.

In this problem, you will be given a set. Your job is to calculate the minimum difference of the sum of two subsets.

 

The Input

The first line of input contains a number T < 100, where T denotes the number of test cases. The first line of each case starts with a positive integer n <= 30, where n denotes the number of elements in the set. The next line contains n space separated positive integers (E1, E2, .. En), those numbers are the set elements (-1000 < E1, E2, .. En < 1000).

 

The Output

For each case of input, there will be one line of output. It will contain the case number followed by the minimum difference of the sum of two subsets.

 

Sample Input

2

8

23 45 34 12 0 3 1 4

5

10 20 30 40 50

 

Sample Output

Case 1: 0

Case 2: 10

 

 

 

Inter University Programming Contest - Summer 2019 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS