C算法优化：从N个元素中找到K个组合

Question

我对C很在行，我正在尝试做一些黑客挑战，以此作为解决这个问题的方法
现在我正在努力解决愤怒的孩子们的问题：https://www.hackerrank.com/challenges/angry-children

基本上，它要求创建一个程序，给定一组N个整数，为该集合的K长度子集找到最小可能的“不公平”。不公平定义为K长度子集的最大值和最小值之间的差值。

我现在要做的是找到所有的K长度子集，计算它们的不公平性，跟踪最小的不公平性。

我编写了以下C程序，似乎正确地解决了这个问题：

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int unfairness = -1;
int N, K, minc, maxc, ufair;
int *candies, *subset;

void check() {
    ufair = 0;
    minc = subset[0];
    maxc = subset[0];

    for (int i = 0; i < K; i++) {
        minc = min(minc,subset[i]);
        maxc = max(maxc, subset[i]);
    }

    ufair = maxc - minc;

    if (ufair < unfairness || unfairness == -1) {
        unfairness = ufair;
    }
}

void process(int subsetSize, int nextIndex) {
    if (subsetSize == K) {
        check();
    } else {
        for (int j = nextIndex; j < N; j++) {
            subset[subsetSize] = candies[j];
            process(subsetSize + 1, j + 1);
        }
    }
}

int main() {
    cin >> N >> K;
    candies = new int[N];
    subset = new int[K];

    for (int i = 0; i < N; i++)
        cin >> candies[i];

    process(0, 0);

    cout << unfairness << endl;

    return 0;
}

问题是HackerRank要求程序在3秒内找到解决方案，而我的程序需要更长的时间才能找到12/16个测试用例的解决方案。例如，其中一个测试用例的N=50和K=8；程序需要8秒钟才能在我的机器上找到解决方案。我可以做些什么来优化我的算法？我对C语言不是很有经验。

Answer 1

我的一个建议是在选择子集之前对整数列表进行排序。这将大大减少需要检查的子集的数量。事实上，您甚至不需要创建子集，只需查看索引i（从0开始）和ik处的元素，i和ik处所有元素的最低差值[有效边界]就是您的答案。因此，现在您不必选择n个子集（我相信是阶乘运行时），而只需查看~n个子集（线性运行时），排序（nlogn）就会成为性能瓶颈。

Answer 2

你所要做的就是对所有的数字进行升序排序，然后得到最小的a[i K-1]-a[i]所有i从0到N-K>包括在内。这是真的，因为在最优子集中，所有数字都依次位于排序数组中。