java查找数组的所有组合，并获取前k个和元素

Question

我有一个数字数组，比如[1,2,3,11000]，现在我想得到这个数组的所有可能组合，并计算它的和。组合是有效的，因此两个组合具有不同的元素子集。然后按降序排列所有和值，得到前k个元素

示例：

[1,2,3,1,1000]

组合：

较早版本的副本被删除，例如（3,1）匹配较早版本（1,3）

（1），（2），（3），（1），（1000），（1,2），（1,3），（1,1），（11000），（2,1），（21000），（3,1），（31000），（11000），（1,2,3），（1,2,1），（1,21000），（1,11000），（1,3,1），（2,3,31000），（2,31000），，，（2,3,11000），，，，（1,2,3,1），（1,2,31000），（1,2,11000），（1,3,11000），（2,3,11000），（1,2,3,11000）

以及相应的金额：

0,1,2,3，1，1000,3,4,2,1001,5，3，1002，4，1003，1001，6,4,1003,5,1004,1002，6，1005，1004，7,1006,1004,1005，

Getting top k=3, sums = 1007, 1006, 1005

So output is [1007, 1006, 1005].

约束条件：

• 数组大小n=1到10⁵
• 数组元素-10⁹到10⁹
• k的范围从1到2000

这是我的代码，引用自here：

static List<Long> printDistSum(int arr[]) {
        List<Long> list = new ArrayList<>();
        int n = arr.length;
        // There are totoal 2^n subsets
        long total = (long) Math.pow(2, n);
        
        // Consider all numbers from 0 to 2^n - 1
        for (int i = 0; i < total; i++) {
            long sum = 0;

            // Consider binary representation of
            // current i to decide which elements
            // to pick.
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0)
                    sum += arr[j];

            // Print sum of picked elements.
            list.add(sum);
        }
        return list;
    }

此代码适用于小范围的输入，但适用于大范围的输入。如何解决这个问题

Answer 1

我可能有足够好的解决方案。它的时间复杂度为O（n*k*log（k））

首先，我们需要计算所有正值的最大和

接下来我们需要迭代正值，从最小值到最大值。对于这些值中的每一个，我们计算新组合的和（开始时，我们有一个最大和的组合）。 新的组合不会包含给定的值，所以我们需要从总和中减去它

最后，我们需要迭代负值。这些值不属于上一步的组合，所以我们需要将这些值添加到总和中

每次迭代只需要k个最大和。我使用PriorityQueue来存储这些总数。该类使用堆数据结构，因此添加/删除值需要对数时间

代码：

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 ;)
}

演示：https://ideone.com/yf6POI

编辑：我已经修复了我的解决方案。我没有迭代不同的值，而是检查当前值是否与前一个值相同。在这种情况下，我使用上一步创建的组合（和）。这样可以防止创建重复的组合

如果我解释得不够好，我很抱歉。我没有用英语描述算法/数学方面的经验