Tug of War

Posted: 24 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are a coach of a group consisting of 'N' students. The ith student has a strength Arr[i]. For a Tug of War game, you want to divide students into two teams of equal size (If N is odd, then size of one team should be (N-1)/2 and size of other team should be (N+1)/2). You want a game that is fun, for this the absolute difference between the team’s strength should be as minimum as possible. A team's strength is the sum of the strengths of the students in the team.

Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 

Then the 'T' test cases follow.

The first line of each test case contains a positive integer 'N', which represents the number of students.

The next line contains 'N' single space-separated integers representing the strength of the students.
Output Format :
For each test case, print the minimum absolute difference between the team’s strength.

The output of each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= N <= 20
0 < Arr[i] <= 10^5
Where T is the number of test cases, N is the number of students and Arr[i] is the strength of ith student.
Approach 1

The idea is to find all possible subsets of size N/2.

Let’s say we have a subset of size N/2, ‘subsetSum’ will be the sum of strength of this subset and ‘totalSum’ will be the sum of strength of all N students. Then, the absolute difference between the team’s strength will be | (totalSum - subsetSum) - subsetSum |, which is equal to | totalSum - 2 * subsetSum |.
 

We will use recursion to find the subset.
 

Algorithm:

Let’s define a function tugOfWarHelper(i, subsetSum, cnt, totalSum), where i is the current index, subsetSum is sum of strength in the subset and cnt is the number of students in the subset. This function returns the minimum absolute difference.

Each student has two choices: either it will be included in the current subset or not.
 

Base Case: 

If i is equal to N:

  • If cnt is equal to N/2, return absolute difference,i.e, | totalSum -2* subsetSum |.
  • Else, return an infinite value (INT_MAX)
     

Recursive States:

Return minimum of :

  • tugOfWarHelper(i + 1, subsetSum, cnt, totalSum)
  • tugOfWarHelper(i + 1, subsetSum + Arr[i], cnt + 1, totalSum)
Try Problem