Java | Merge Sort | O(n) + O(k^2)
\n    public long kSum(int[] nums, int k) {\n        //get sum \n        long sum = 0;\n        for(int i = 0; i < nums.length; i ++ ){\n            if(nums[i] 
\n    public long kSum(int[] nums, int k) {\n        //get sum \n        long sum = 0;\n        for(int i = 0; i < nums.length; i ++ ){\n            if(nums[i] > 0){\n                sum += nums[i];\n            }else{\n                nums[i] *= -1;\n            }\n        }\n        \n        //sort  increasing.\n\t\t//=> sum - 0, sum - a0, .., sum - an, => find an, which is the kth smallest sum in nums.\n        Arrays.sort(nums);\n\n        \n        ArrayList<Long> a = new ArrayList<>();\n        ArrayList<Long> b = new ArrayList<>();\n        a.add(0L);\n        //merge sort. merge a and a + nums[i]\n        //let b always <= k, stop at i == k\n        // a1: [0,n], a2: [0,n+1], aka, a1 + x\n        for(int i = 0; i < nums.length && i < k; i ++ ){\n            int x = nums[i];\n            int p1 = 0, p2 = 0;\n            b.clear();\n            \n            while(p1 < a.size() && p2 < a.size() && b.size() < k){\n                if(a.get(p1) < a.get(p2) + x){\n                    b.add(a.get(p1));\n                    p1++;\n                }else{\n                    b.add(a.get(p2) + x);\n                    p2++;\n                }\n            }\n            \n            while(p1 < a.size() && b.size() < k){\n                b.add(a.get(p1));\n                p1++;\n            }\n            \n            while(p2 < a.size() && b.size() < k ){\n                b.add(a.get(p2) + x);\n                p2++;\n            }\n            \n            ArrayList<Long> tmp = a;\n            a = b;\n            b = tmp;\n        }\n        \n        \n        return sum - a.get(k - 1);\n    }
[]