Share My Solution | Explanation with Logic in code |  C++
Preriquisites:\nMerge Sorted Array\nPriority Queue (Heap)\nSubsets\n\nTime Complexity: O( nlog(n) + k + klog(k) )\n\nSpace Complexity: O( n + k )\n\n/*\n    Log
**Preriquisites:**\n[Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)\nPriority Queue (Heap)\n[Subsets](https://leetcode.com/problems/subsets/)\n\n**Time Complexity:** O( n*log(n) + k + k*log(k) )\n\n**Space Complexity:** O( n + k )\n```\n/*\n    Logic:\n    \n    The largest sum possible is the sum of all positive elements.\n    \n    Now we have to consequently decrease some amount from this largest sum.\n    \n    We have to do this k times.\n    \n    Like num= [-1,1,2,3]\n    sum=6\n    \n    All possible seq in decreasing order =[6,5,5,4,4,3..]\n    \n    It is same as: [6-0,6-1,6-1,6-2,6-2,6-3,...]\n    \n    Here every time, we are subtracting some elements from largest sum. \n    \n    Example   2 = {1+2+3} - {2,1} + {-1}\n    \n                {Largest Sum} - {sum of some Positive elements} + {sum of some negative elements}\n    \n    Here any number is derived by removing some positive elements from largest sum and adding some negative elements to sum.\n    \n    How to decide which positive numbers to be removed and which negative numbers to be added?\n    \n    There will be so many subsets of positive as well as negative elements.\n    \n    We will generate k+1 smallest subset sums of positive and negative numbers separately. (k non-empty and 1 empty subset)\n    \n    Now there might be (k+1)*(k+1) ways to choose positive and negative subsets.\n    \n    \n    \n    But note that:\n    \n    Let us denote (i,j) as the sum of i\'th smallest positive subset and j\'th smallest negative subset  \n    Then (i,j) < (i,j+1). Since both positive and negative subset sums are sorted.\n    \n    Using above fact we can reduce the time complexity from O(k*k) to O(k*log(k))\n    \n    We will use one priority queue.\n    Initially push all pairs (0,0) (1,0) (2,0) ... (k,0) in priority queue.\n    \n    Priority queue will give us the pair which is having smallest sum.\n    Let us consider, it as (i,j) then now we will push (i,j+1) to the priority queue.\n    \n    We will repeat this process k times, since we want k\'th smallest number\n    \n*/\n\nclass Solution {\npublic:\n    \n    /*\n        For a given array of lenth n, there are 2^n possible subsets.\n        Since we have 2 options for every element to take or not.\n        \n        How subset sum works?\n        \n        example: nums=[1,2,3,4]\n        Keep previous records as it is and add all records with sum of new element\n        \n        Initially ans={0}\n        \n        Added 1: {0,(0+1)}={0,1}\n        Added 2: {0,1,(0+2),(1+2)}={0,1,2,3}\n        Added 3: {0,1,2,3,(0+3),(1+3),(2+3),(3+3)}={0,1,2,3,3,4,5,6}\n        \n        It appears that subset sums calculated in this way will always be sorted. Right?\n        \n        Added 4: {0,1,2,3,3,4,5,6,{0+4},{1+4},{2+4}...} ={0,1,2,3,3,4,5,6,4,5,6,...}\n        \n        It is not sorted, as we can see in the last step.\n        \n        But we want k smallest subset sums.\n        \n        How to do that?\n        \n        Take new vector/array called newRecords. Keep ans as it is. ans is sorted already. \n        Calculate newRecords.\n        \n        In the given example: \n        ans       ={0,1,2,3,3,4,5,6}\n        newRecords={4,5,6,7,7,8,9,10} Added 4\n        \n        Merge ans and newRecords into new vector called newAns.\n        Here both ans and newRecords both are sorted. So we will use.\n        \n        newAns=   {0,1,2,3,3,4,4,5,5,6,6,7,7,8,9,10}\n        Use this newAns as ans for next iterations\n    */\n    \n    void makeSubsetSum(vector<int>&nums,int k,vector<long long>&ans){\n        //function which calculates k smallest subset sums of nums\n\n        ans.push_back(0ll);//0 for the empty subset\n        \n        for(int i=0;i<nums.size();i++){\n            \n            //We are trying to add nums[i] to previously added records\n            vector<long long int>newRecords;\n            \n            //There are two scenarios \n            //1. ans is having records less than k\n            //2. ans is having records exactly equal to k\n            \n            //In the second scenario, \n            //if the (nums[i]+ans[j]) is greater than greatest element in the ans, \n            //then it will not be the part of the final ans (kind of pruning)\n            for(int j=0;j<ans.size()&&(ans.size()<=k||(nums[i]+ans[j])<ans.back());j++){\n                newRecords.push_back(nums[i]+ans[j]);\n            }\n            \n            \n            if(newRecords.size()==0){\n                //No new records added, so we can break\n                break;\n            }\n            \n            vector<long long int>newAns;\n            \n            //merging starts\n            int ii=0,jj=0;\n            while(ii<ans.size() && jj<newRecords.size() && newAns.size()<=k){\n                if(ans[ii]<newRecords[jj]){\n                    newAns.push_back(ans[ii]);\n                    ii++;\n                }else{\n                    newAns.push_back(newRecords[jj]);\n                    jj++;\n                }\n            }\n            \n            while(ii<ans.size() && newAns.size()<=k ){\n                newAns.push_back(ans[ii]);\n                ii++;\n            }\n            \n            while(jj<newRecords.size() && newAns.size()<=k ){\n                newAns.push_back(newRecords[jj]);\n                jj++;\n            }\n            //mering ends\n            \n            swap(ans,newAns);\n        }\n        \n    }\n    \n    \n    long long kSum(vector<int>& nums, int k) {\n        \n        vector<int>pos,neg;\n        long long int sum=0;\n        \n        //separate out the positive and negative elements\n        for(int num:nums){\n            if(num>=0){\n                sum+=num;\n                pos.push_back(num);\n            }else{\n                neg.push_back(-num);\n            }\n        }\n        \n        //sort them\n        sort(pos.begin(),pos.end());\n        sort(neg.begin(),neg.end());\n        \n        vector<long long>subsetPos,subsetNeg;\n        \n        // Calculate first smallest k subset sums for positive and negative elements\n        makeSubsetSum(pos,k,subsetPos);\n        makeSubsetSum(neg,k,subsetNeg);\n        //Now we have k smallest subset sums\n        \n        //Comaparator for priority queue\n        auto comp=[&](pair<int,int>&a,pair<int,int>&b){\n        \n            long long int first=subsetPos[a.first]+subsetNeg[a.second];\n            long long int second=subsetPos[b.first]+subsetNeg[b.second];\n            \n            //refer stack overflow\n            \n            return first>second;\n        };\n        \n        //https://stackoverflow.com/questions/5807735/c-priority-queue-with-lambda-comparator-error\n        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(comp)>pq(comp);\n        \n        for(int i=0;i<subsetPos.size();i++){\n            pq.push(make_pair(i,0));\n        }\n        \n        long long int ans=sum;\n        \n        for(int i=0;i<k;i++){\n            \n            pair<int,int>p=pq.top();\n            pq.pop();\n            \n            long long int fromPos=p.first,fromNeg=p.second;\n            \n            ans=sum-subsetPos[fromPos]-subsetNeg[fromNeg];\n            \n            if(fromNeg+1<subsetNeg.size()){\n                pq.push(make_pair(fromPos,fromNeg+1));\n            }\n            \n        }\n        \n        return ans;\n    }\n};\n```
['C', 'Heap (Priority Queue)', 'C++']