Minimum Subset Difference

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

/* An optimization can be added in the code:

 RULES: If the original array is of size n
 n: even
 each set should be of size: n/2

 n: odd
 one of the set would be of size n / 2, and other would be of (n / 2) + 1

 So while making recursive calls, we can track the size of the set, if the size of the current set is less than (n + 1)/2 then only we can add a number in the set and call further

 so for n = 6
 (n + 1) / 2 = 3
 so either of the set will include the current number only if the size of that set < 3 because if something is added here, no solutions will be formed moving further into the branch as we added more numbers that were required to one of the sets and it would violate the size difference rule.

 for n = 7
 (n + 1) / 2 = 4
Either of the set will include the current number only if the size is of that set at the time of calling is < 4. for a set with size = 3, it can call, it size would increase to 4, and now the other set would automatically be of size 3. Same analogy follows as for n = 6.
*/
void minSubsetSumDiff(int index, int sum1, int sum2, int &minDiff, vector<int> &v, vector<int> &v1, vector<int> &v2, vector<vector<int> > &result){
    //base case
    if(index >= v.size()){
        /*
        1. n = even, both subset of same size
        2. n = odd, difference between the subset size should be 1
        */
        if((int) v.size() % 2 == 0){
            if((int) v1.size() == (int) v.size() / 2){
                if(abs(sum1 - sum2) < minDiff){
                    minDiff = abs(sum1 - sum2);
                    while(!result.empty()){
                        result.pop_back();
                    }
                    result.push_back(v1);
                    result.push_back(v2);
                }
            }
        }
        else{
            if(abs((int) v1.size() - (int) v2.size()) == 1 && abs(sum1 - sum2) < minDiff){
                minDiff = abs(sum1 - sum2);
                    while(!result.empty()){
                        result.pop_back();
                    }
                    result.push_back(v1);
                    result.push_back(v2);
            }
        }
        return;
    }

    // level / current element chooses to go into the left partition
    v1.push_back(v[index]);
    minSubsetSumDiff(index + 1, sum1 + v[index], sum2, minDiff, v, v1, v2, result);
    v1.pop_back();

    // level / current element chooses to go into the right partition
    v2.push_back(v[index]);
    minSubsetSumDiff(index + 1, sum1, sum2 + v[index], minDiff, v, v1, v2, result);
    v2.pop_back();
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    vector<int> v1, v2;
    vector<vector<int> > result;
    int minDiff = INT_MAX;
    minSubsetSumDiff(0, 0, 0, minDiff, v, v1, v2, result);
    for(int i = 0; i < result.size(); i++){
        cout << '[';
        for(int j = 0; j < result[i].size(); j++){
            cout << result[i][j] << ',';
        }
        cout << "]\n";
    }
}