Partition a set into two subsets such that the difference of subset sums is minimum.

PROBLEM STATEMENT

You are given an array containing N non-negative integers. Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

1. Each element of the array should belong to exactly one of the subset.

2. Subsets need not be contiguous always. For example, for the array : {1,2,3}, some of the possible divisions are a) {1,2} and {3}  b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset.

Input Format:

The first line of input contains the integer T, denoting the number of test cases.

The first line of each test case contains an integer N, denoting the size of the array.

The second and the last line of each test case contains N space-separated integers denoting the array elements.

Output Format:

For each test case, return the minimum possible absolute difference 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
1 <= N <= 10^3
0 <= ARR[i] <= 10^3
0 <= SUM <= 10^4, 

where SUM denotes the sum of all elements in the array for a given test case.

Time Limit: 1sec

Approach 1

This problem can be solved using recursion. And the idea behind this is to generate all the possible sums from the given set.
We will try different combinations for one of the subsets and accordingly calculate the sums of both the subsets and store the minimum. Assume that the sum of elements of the array is SUM, and sum of the elements of the first subset is S1, thus we can find the sum of 2nd subset as SUM - S1.
For each element we will have two choices: either to include it in the first subset or not. So, at each stage, we will make two recursive calls, one which will consider including the current element and other which won’t. We will explore the depth taking into consideration each of the two possible cases.
When we have no elements to explore we will consider |TOTAL_SUM - 2 * PATH_SUM | (ABS((TOTAL_SUM - PATH_SUM) - PATH_SUM)| as one of the possible answers. And finally, we will be taking the minimum of all such values to get the desired answer.

Try Problem

Approach 2

We can think of this problem as the standard problem of dynamic programming, which is to check whether there exists a subset with the given SUM.

Since here we need to find if there is a way to partition a set into two subsets such that the difference between subset sums is minimum. We know that the best possible scenario is when the subset sums of both the subsets are equal, and thus we want both our subsets to have a SUM as close to SUM/2 is the total sum of elements in the array. So to achieve this we need to check if there exists a subset with SUM up to half the total sum.

So, to do this we will create a boolean DP table of size ((N+1) * (SUM/2 + 1)), where the sum is the total sum of the array, and n is the number of elements in the array.
Here, the value of DP[i][j] denotes whether or not it is possible to make a subset from the first i elements of the array with SUM equal to j.
The base case will be DP[i][0]=true, and DP[0][j]=false for j>0.
Now the loop(loop variable-i) runs through the number of elements:
- Now loop(loop variable-j) runs through 1 to (SUM/2 + 1):
  - If the value of ith element is equal to j DP[i][j]=true.
  - If value of ith element is greater than j then we cant consider the ith element to achieve the sum = j, and thus DP[i][j]=DP[i-1][j]
  - If the value of ith element is less than j then the value of DP[i][j] would be DP[i][j]=DP[i-1][j] | DP[i-1][j-VAL[ith ELEMENT]] (| denotes boolean ‘or’), where VAL[ith ELEMENT] corresponds to the value of the ith ELEMENT because here we have two possibilities: to include the ith element or to leave it.
Now after computing the DP table as above, we can run a loop for all the columns of the last row from right to left and at whichever value of j the value in the table is true we will return ABS(TOTAL_SUM - 2*j), which is our best possible answer.

Try Problem