Partition Problem - Karmarkar Karp Algorithm

This is an implementation of the Karmarkar-Karp algorithm in O(nlogn) steps.

The Karmarkar-Karp heuristic begins by sorting the numbers in decreasing order. At each step, the algorithm commits to placing the two largest numbers in different subsets, while differencing the decision about which subset each will go in. The algorithm continues removing the two largest numbers, replacing by their difference in the sorted list, until there is only one number left, which is the value of the final subset difference. If the final subset difference is equal to 0, then partition is possible else not possible.

Following is the implementation of the algorithm in C++ and note that this algorithm better than the Dynamic Programming Approach because Dynamic approach takes longer time for large value of sum.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
   vector<int>v={3, 1, 1, 2, 2, 1};
   sort(v.begin(),v.end());
   int a;
   while(v.size()!=1){
        auto i = v.end()-1;
        a = (*(i))-(*(i-1));
        v.pop_back();
        v.pop_back();
        v.push_back(a);
        sort(v.begin(),v.end());
   }
   if (a==0)
        cout<<"Partition is Possible";
    else
        cout<<"Partition is not Possible";


}
I will soon update the code of the algorithm, so that you can also find the two subsets partition elements. Till then enjoy the game of partitions.