import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) {
        int[] array = {1, 2, 1, 3, 1000};
        System.out.println(Arrays.toString(findSums(array, 3)));
    }

    private static long[] findSums(int[] array, int k) {
        long maxSum = Arrays.stream(array).filter(it -> it >= 0).sum();

        int[] positives = Arrays.stream(array).filter(it -> it >= 0).sorted().toArray();
        int[] negatives = Arrays.stream(array).filter(it -> it < 0).sorted().toArray();
        // sort time complexity is O(n*log(n))

        PriorityQueue<Long> sums = new PriorityQueue<>(k); // priority queue is implemented using heap so adding element has time complexity O(log(n))
        sums.add(maxSum); // we start with max sum - combination of all positive elements

        int previous = Integer.MIN_VALUE;
        Long[] previousAddedSums = {};
        Long[] sumsToIterate;

        // iterate over positive values
        for (int i = 0; i < positives.length; i++) {
            if (positives[i] == previous) {
                sumsToIterate = previousAddedSums;
            } else {
                sumsToIterate = sums.toArray(new Long[sums.size()]);
            }
            previousAddedSums = new Long[sumsToIterate.length];
            for (int j = 0; j < sumsToIterate.length; j++) {
                long newSum = sumsToIterate[j] - positives[i];
                // new sum is calculated - value positives[i] is removed from combination (subtracted from sum of that combination)
                sums.add(newSum);
                previousAddedSums[j] = newSum;
                if (sums.size() > k) {
                    sums.poll(); // only first k maximum sums are needed at the moment
                }
            }
            previous = positives[i];
        }

        previous = Integer.MAX_VALUE;
        // iterate over negative values in reverse order
        for (int i = negatives.length - 1; i >= 0; i--) {
            if (negatives[i] == previous) {
                sumsToIterate = previousAddedSums;
            } else {
                sumsToIterate = sums.toArray(new Long[sums.size()]);
            }
            previousAddedSums = new Long[sumsToIterate.length];
            for (int j = 0; j < sumsToIterate.length; j++) {
                long newSum = sumsToIterate[j] + negatives[i]; // value negatives[i] is added to combination (added to sum of that combination)
                sums.add(newSum);
                previousAddedSums[j] = newSum;
                if (sums.size() > k) {
                    sums.poll();
                }
            }
            previous = negatives[i];
        }

        long[] result = new long[sums.size()];
        for (int i = sums.size() - 1; i >=0 ; i--) {
            result[i] = sums.poll();
        }
        // get sums from priority queue in proper order
        return result;

        // this whole method has time complexity O(n * k * log(k))
        // k is less than or equal 2000 so it should be good enough ;)
    }

}