# Minimum Sum Partition

Given an array, the task is to divide it into two sets *S1* and *S2* such that the absolute difference between their sums is minimum.

**Problem Description:** The given problem wants you to find two subsets such that you utilize all the elements of the array and then you are required to find the difference between the two set such that their difference is minimum. It might be possible that it has many subsets satisfying the above criteria but you need to print the difference of that subset whose difference is minimum.

**Input:** The first line contains an integer '*T*' denoting the total number of test cases. In each test case, the first line contains an integer '*N*' denoting the size of the array. The second line contains N space-separated integers *A1*, *A2*, ..., *AN* denoting the elements of the array.

**Output:** In each separate line print minimum absolute difference.

**Example:**

Input:
T = 1
N = 5
[5,4,6,9,3]
Output:
1
Explanation:
S2 = {9,5} And S1 = {4,6,3}.
S2-S1 = 14-13 = 1
Input:
T = 1
N = 6
[2,7,4,1,8,1]
Output:
1
Explanation:
S2 = {8,4} And S1 = {7,2,1,1}. S2-S1 = 1.

This problem is a variation of the subset sum problem. Since here we are not given the size of two subsets, but we are sure that the value in single subset lies between 0 and sum of the array. If we can get the value in a single subset then it is very easy to obtain the value of the other subset. We just subtract it from the total sum to get the sum of values of elements in the second subset.

We need to find the subsets which are present in the array from the value sum/2 to 0, we will check each of these value in the array whether it is possible to obtain the subset or not? To confirm whether we obtained the correct value or not we will use subset-sum logic in this problem:

Therefore, the problem reduces to:

Where,

dp[n][i]is the value of subset-sumiobtained usingnelements. The value of the second subset is obtained as(sum-i). Therefore, the overall difference of two sets is obtained ass2-s1=(sum-i)-i,i.e(sum-2*i), whereineed to be as close tosum/2for the minimum difference.Time complexityfor the above approach in worst cases:O(n*n)Space complexityfor the above approach in worst cases:O(n*n)Program to illustrate the solution

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