Two subsets with minimum difference

Question

Consider an array arr.

s1 and s2 are any two sub sets of our original array arr. We should partition our original array such that these two sub sets have the minimum difference, i.e., min(sum(s1) - sum(s2)) where sum(s1) >= sum(s2).

I'm supposed to print these two sub sets, i.e., s1 and s2, as my output.

You can store these sub sets in a vector.

For example if arr[] = [0,1,5,6], then the minimal difference is 0 and my two sub sets are s1[] = [0,1,5] and s2[] = [6].

Another example could be arr[] = [16,14,13,13,12,10,9,3], and the two sub sets would be s1[]=[16,13,13,3] and s2[] = [14,12,10,9] with a minimum difference of 0 again.

I can't seem to figure out how to get to these two sub sets.

Much appreciated!

Note: I know how to obtain the minimum difference from the two sub sets using DP but I am unable to proceed further. It's getting the two sub sets (with the minimal difference) that I'm unable to do. Just an algorithm with a nudge along the right direction would do.

#include<iostream>
#include<vector>
using namespace std;

int min_subset_sum_diff(int a[], int n,int sum) {
    vector<vector<bool>> go(n + 1, vector<bool>(sum + 1, false));
    for (int i = 0; i < n + 1; ++i) {
        go[i][0] = true;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= sum; ++j) {
            if (a[i - 1] <= j) {
                go[i][j] = go[i - 1][j - a[i - 1]] || go[i - 1][j];
            }
            else {
                go[i][j] = go[i - 1][j];
            }
        }
    }
    for (int j = (sum / 2); j >= 0; --j) {  
        if (go[n][j]) {                  // only need the last row as I need all the elements, which is n
            return sum - 2 * j;
        }
    }
    return INT_MAX;
}

int main() {
    int a[] = { 3,100,4,4 };
    int n = sizeof(a) / sizeof(a[0]);
    int sum = 0;
    for (auto i : a) {
        sum += i;
    }
    cout << min_subset_sum_diff(a, n,sum);
}

s1 = sum(first_subset)

s2= sum(second_subset)

Assuming s2>=s1,

s1 + s2 = sum_arr
s2 = sum_arr - s1       //using this in the next equation
s2-s1 = difference
(sum_arr - s1) - s1 = difference 
sum_arr - 2*s1 = difference

This is my underlying logic.

sum(s1) and sum(s2) lie between 0..sum_arr

Since I assume s1 < s2, s1 can have values only between 0..(sum_arr/2)

And my aim is to minimum value of sum_arr - 2*s1, this will be true for the largest s1 that is true

if you know how to get the minimum difference via DP you just need to remember the partionion along with the minimum difference you calculate — 463035818_is_not_an_ai, Aug 21 '20 at 18:06
@user123456 Probably because seems likely to be homework, have been asked before, and solutions like https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/ are an easy Google search away. — btilly, Aug 21 '20 at 18:25
This was actually a technical F2F interview question. And I haven't found any solution that actually partitions the array into two sub arrays. All solutions only output the minimum difference. I did my research before asking it over here. — user123 456, Aug 21 '20 at 18:28
@user123456 See https://stackoverflow.com/a/63362010/585411 for my solution to a variant of this problem. (Find all subsets of fixed size that sum to a given sum. Without duplicates.) If you can understand the way I used linked lists there, then the solution to this one should be easy. It will, of course, only output the set that sums to one half, you have to go back and figure out the complement of that set. — btilly, Aug 21 '20 at 18:39
For your simpler problem, I would simply build a lookup from subset sum to the first element of the array which is the last element in a subset giving that sum. Then use that lookup to find the one set, and calculate its complement for the other. — btilly, Aug 21 '20 at 18:40
@TedLyngmo The request is that the sum of one subset minus the sum of the other is as small as possible. This is the subset sum problem except actually find the elements. — btilly, Aug 21 '20 at 18:41
You shouldn't ask a question, delete it because you don't like the comments and ask the exact same question one hour later. — Thomas Sablik, Aug 21 '20 at 18:41
@ThomasSablik I don't understand how that answers my question. If at all I could get the first sub array, then what you've said is obvious. The whole challenge is getting the sub array. Care to explain how you would get the first sub array? — user123 456, Aug 21 '20 at 19:03
I don't understand why there are so many down votes. This isn't really an easy question and I haven't found any solution online. Can someone explain to me why they're down voting? Was it how I phrased my question? — user123 456, Aug 21 '20 at 20:16
Look at the answer posted by @MBo for a more detailed explanation of one way to do my simpler approach. I personally will not offer you more help until I see evidence that you've attempted to do something with answers that you've already been given. — btilly, Aug 21 '20 at 20:26
@btilly I understand. I'll try summing everything I've got here and try to come up with something. You've honestly been the only helpful one. I appreciate it. Cheers! — user123 456, Aug 21 '20 at 20:37
@btilly The updated question cleared up the ambiguity I was referring to. — Ted Lyngmo, Aug 23 '20 at 09:41

score 1 · Answer 1 · answered Aug 21 '20 at 19:38

Make parallel table of int T[][] with the same dimensions as go[][]

When you make a decision here

if (a[i - 1] <= j)

put in T[i][j] some kind of information pointing onto true precursor coordinates for go[i][j]

After filling the tables you search for the best true entry in go[n] row of boolean table. When it is found, get value from the same cell of T table and follow to precursor, then to precursor of prcursor and so on ("unwind" subset information)

Two subsets with minimum difference

1 Answers1