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-sum i obtained using n elements. The value of the second subset is obtained as (sum-i). Therefore, the overall difference of two sets is obtained as s2-s1=(sum-i)-i,i.e (sum-2*i), where i need to be as close to sum/2 for the minimum difference.
Time complexity for the above approach in worst cases: O(n*n)
Space complexity for the above approach in worst cases: O(n*n)
Program to illustrate the solution
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer