Minimum Subset sum difference problem with Subset partitioning | meet in the middle | MUST DO | OA

https://practice.geeksforgeeks.org/problems/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum-set-2/1
article (author: Abhijit)- https://www.geeksforgeeks.org/minimum-subset-sum-difference-problem-with-subset-partitioning/


Given a set of N integers with up to 40 elements, the task is to partition the set into two subsets of equal size (or the closest possible), such that the difference between the sums of the subsets is minimized. If the size of the set is odd, one subset will have one more element than the other. If the size is even, both subsets will have the same size. After finding the minimum difference, output the subsets.

Examples:

Input: arr[] = {45, 34, 4, 12, 5, 2}
Output: Min Difference 0 Subset 1 : {34, 12,  5} Subset 2 : {45,  4,  2}
Explanation: The above generated two subsets have sum
∑ Subset 1 : 34+12+5 =  51
∑ Subset 2 : 45+4+2 =  51
The minimum difference is abs( ∑ S1 – ∑ S2 ) = 0, which is the minimum difference possible.

Input: arr[] = {3, 34, 4, 12, 5, 2 }
Output: Min Difference 18 Subset 1 : {3  34  2} Subset 2 : {4  12  5 }
Explanation: The above generated two subsets have sum
∑ Subset 1 : 3+34+2 =  39
∑ Subset 2 : 4+12+5 =  21
The minimum difference is abs( ∑ S1 – ∑ S2 ) = 18, which is the minimum difference possible.

---------------------------------------------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;

struct Info {
    int sum;
    vector<int> indices;
};

static bool cmp(Info& p1, Info& p2)
{
    return p1.sum < p2.sum;
}

void generate(vector<int>& arr, int curr, int n, int sum,
            vector<vector<Info> >& store,
            vector<int> build)
{
    if (curr == n) {
        int sz = build.size();
        store[sz].push_back({ sum, build });
        return;
    }
    build.push_back(curr);
    generate(arr, curr + 1, n, sum + arr[curr], store,
            build);
    build.pop_back();
    generate(arr, curr + 1, n, sum, store, build);
}

int BINRY_SRCH(vector<Info>& arr, int target)
{

    // Lower bound
    int res = -1;
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid].sum >= target) {
            res = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return res;
}

vector<vector<int> > minDifference(vector<int>& arr, int n)
{
    int extra = (n % 2 != 0);

    vector<vector<Info> > part1(n / 2 + 1 + extra);
    vector<vector<Info> > part2(n / 2 + 1);

    generate(arr, 0, n / 2 + extra, 0, part1, {});
    generate(arr, n / 2 + extra, n, 0, part2, {});

    for (auto& vec : part2) {

        // Sorting part2 to prepare
        // for binary search
        sort(vec.begin(), vec.end(), cmp);
    }

    vector<vector<int> > res(2);

    int diff = INT_MAX;
    int TS = accumulate(arr.begin(), arr.end(), 0);

    // Making subset1
    for (int ele = 1; ele <= n / 2 + extra; ele++) {

        // Taking only ele
        // elements from part1
        vector<Info> P1 = part1[ele];

        // Taking rest of the elements
        // for subset1 from part2
        vector<Info> P2 = part2[n / 2 + extra - ele];

        // Iterating for each sum in P1
        for (auto x : P1) {

            // P1sum -> subset1 sum
            // P2sum -> subset2 sum

            // For absolute minimisation,
            // each subset should be having
            // sum close to TS/2. If we
            // take x sum from Part1, then
            // remaining sum TS/2-x should
            // be taken from part2. We
            // want to get a sum closer to
            // this target. For this, do
            // binary search.
            int index = BINRY_SRCH(P2, TS / 2 - x.sum);
            if (index != -1) {
                int subset1_Sum = x.sum + P2[index].sum;
                int subset2_Sum = TS - subset1_Sum;

                if (abs(subset1_Sum - subset2_Sum) < diff) {
                    diff = abs(subset1_Sum - subset2_Sum);

                    // Storing the subset
                    vector<int> subset1 = x.indices;
                    for (auto c : P2[index].indices) {
                        subset1.push_back(c);
                    }
                    res[0] = subset1;
                }
            }

            if (index > 0) {
                index--;
                int subset1_Sum = x.sum + P2[index].sum;
                int subset2_Sum = TS - subset1_Sum;

                if (abs(subset1_Sum - subset2_Sum) < diff) {
                    diff = abs(subset1_Sum - subset2_Sum);

                    // Storing the subset
                    vector<int> subset1 = x.indices;
                    for (auto c : P2[index].indices) {
                        subset1.push_back(c);
                    }
                    res[0] = subset1;
                }
            }
        }
    }

    // Find subset2 after ignoring elements
    // of subset1 in arr

    vector<bool> vis(n, false);

    for (int i = 0; i < res[0].size(); i++) {
        vis[res[0][i]] = true;
        res[0][i] = arr[res[0][i]];
    }

    vector<int> subset2;
    for (int i = 0; i < n; i++) {
        if (vis[i] == false) {
            subset2.push_back(arr[i]);
        }
    }
    res[1] = subset2;

    cout << "Min Difference " << diff << endl;

    return res;
}

void PRINT(vector<vector<int> >& subsets)
{
    cout << "Subset 1 : ";
    for (auto x : subsets[0]) {
        cout << x << " ";
    }
    cout << endl
        << "Subset 2 : ";
    for (auto x : subsets[1]) {
        cout << x << " ";
    }
}

int main()
{
    vector<int> arr;
    vector<vector<int> > res;

    arr = {45, 34, 4, 12, 5, 2 };
    res = minDifference(arr, arr.size());
    PRINT(res);
    return 0;
}


O( 2^(n/2)  * log(2^(n/2)) *  n/2 ),  O(2^(n/2)) is for generating two subsets, O(log(2^(n/2))) for binary searching for each element of part1 in part2, hence the extra n/2 factor.