Beats 100.00%
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    int cnt;

    public long kSum(int[] nums, int k) {
        long right = 0, sum = 0;
        cnt = k - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                sum += nums[i];
            } else {
                nums[i] = -nums[i];
            }
            right += nums[i];
        }

        Arrays.sort(nums);
        long left = -1;

        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            cnt = k - 1;
            dfs(nums, mid, 0);
            if (cnt == 0) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return sum - right;
    }

    private void dfs(int[] nums, long mid, int index) {
        if (index == nums.length || cnt == 0 || mid < nums[index]) {
            return;
        }

        cnt--;
        dfs(nums, mid, index + 1);
        dfs(nums, mid - nums[index], index + 1);
    }
}
```
['Java']