C++ | Binary search + Brute-force solution
\n# Approach\nUse binary-search to search for the possible sum value, which can generate >= k subsets, so that we can find the kth largest sum from that value.\
\n# Approach\nUse binary-search to search for the possible sum value, which can generate >= k subsets, so that we can find the **kth largest sum** from that value.\n\n# Complexity\n- Time complexity: O(NlogN + Klog(|MaxSum| + |MinSum|))\n\n# Code\n```\nclass Solution {\npublic:\n    long long INF = 1e18;\n    void countSubset(vector<int>& nums, int& k, long long& targetSum, int idx, long long curSum, int& cnt) {\n        if (cnt >= k) return;\n        if (idx >= nums.size()) return;\n        if (curSum - nums[idx] >= targetSum) {\n            cnt++;\n            countSubset(nums, k, targetSum, idx+1, curSum - nums[idx], cnt);\n        } else {\n            return;\n        }\n        countSubset(nums, k, targetSum, idx+1, curSum, cnt);\n    }\n\n    long long kSum(vector<int>& nums, int k) {\n        int n = nums.size();\n        long long maxSum = 0;\n        long long minSum = 0;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] >= 0) {\n                maxSum += nums[i];\n            } else {\n                minSum += nums[i];\n                nums[i] = abs(nums[i]);\n            }\n        }\n        sort(nums.begin(), nums.end());\n\n        long long l = minSum;\n        long long r = maxSum;\n        long long ans = -INF;\n        while (l <= r) {\n            long long mid = (l + r) >> 1;\n            int cnt = 1;\n            countSubset(nums, k, mid, 0, maxSum, cnt);\n            if (cnt >= k) {\n                ans = max(ans, mid);\n                l = mid + 1;\n            } else {\n                r = mid - 1; // lower right to generate more subsets \n            }\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Recursion', 'C++']