# Tug of War

There is a set contains **N** number of elements. We have to divide this set into two different sets where each of the subsets contains the same number of elements and has a minimum difference between them.

- If
**N** is even then each of the subsets will contain **N/2** number of elements.
- If
**N** is odd then one of the subsets will contain **(N+1)/2** and others will contain **(N-1)/2** number of elements.

Input:
Test case T
//T no. of line with the value of N and corresponding values.
E.g.
3
3
1 2 3
4
1 2 3 4
10
1 4 8 6 -7 -10 87 54 16 100
1<=T<=100
1<=N<=100
Output:
Print the two subsets.

**Example**

T=3
N=3
1 2 3
Output: set1: {1, 2} set2: {3}
N=4
1 2 3 4
Output: set1: {1, 4} set2: {2, 3}
N=10
1 4 8 6 -7 -10 87 54 16 100
Output: set1: {{ 4, -7, -10, 87, 54 } set2: {1, 8, 6, 16, 100 }

Let, there is

Nno. of values, say e1, e2, e3, ..., en andNis even.The process to insert the elements to the Subsets is a problem of combination and permutation. To get the result we use the backtracking process. Here we take the sum of all the elements . Here we have to find out the elements that are in the subset no.1 and the elements that are not in subset1, must be in the subset no. 2. Every time we consider two things.

After getting

N/2number of elements into the subset1. We will check,If the value is less than then

we update the value of theDifferenceand make a note of the elements that are in the subset1.DifferenceAfter getting the elements for those the value of

is less we check the elements of the main set and find out the elements that are not in the subset1 and put them in subset2.Difference1is in the subset1 thereforeSubset1: {1}andDifference = abs(3-1) = 22is in the subset1 thereforeSubset1: {1,2}andDifference = abs(3-3) = 0Therefore,

is minimum.DifferenceC++ implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput