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

Posted: 5 Nov, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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

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