求k聚类集合划分的最小平方和：暴力搜索代码出错求助

你的代码存在几个关键问题，导致运行结果错误：

1. 参数类型错误（致命问题） #

subset函数中的sum参数被定义为int类型，但实际传递的是uint64_t类型的累计平方和。由于题目中的数值极大（样例输出达到10^{16级别），`int`类型的范围（通常仅到2}31-1）完全无法容纳，会导致数值截断、溢出，最终计算出错误的平方和，剪枝逻辑也会失效。

2. 允许生成空子集 #

你的代码会生成空子集并进入递归，这会产生大量无效分支，不仅浪费计算资源，还可能干扰最优解的搜索流程。

3. 剪枝与搜索效率不足 #

未对数组排序，导致大元素的处理顺序靠后，无法快速找到较优解触发剪枝，递归次数过多，甚至可能在有限时间内无法完成计算。

修正后的代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <stdint.h>

bool used[20] = {0};
int n, m;
uint64_t arr[20], min = UINT64_MAX;

// 生成当前子集，仅处理非空子集
void subset(uint64_t subsum, int cur, uint64_t sum, int nset) {
    if (cur == n) {
        // 仅当子集非空时，进入下一轮划分
        if (subsum > 0) {
            find(nset + 1, sum + subsum * subsum);
        }
        return;
    }

    // 剪枝：如果当前元素与前一个元素相同，且前一个未被选中，跳过重复情况
    if (cur > 0 && arr[cur] == arr[cur-1] && !used[cur-1]) {
        subset(subsum, cur + 1, sum, nset);
        return;
    }

    // 不选当前元素
    subset(subsum, cur + 1, sum, nset);

    // 选当前元素（未被使用时）
    if (!used[cur]) {
        used[cur] = true;
        subset(subsum + arr[cur], cur + 1, sum, nset);
        used[cur] = false;
    }
}

void find(int nset, uint64_t sum) {
    // 剪枝：当前累计和已大于等于最优解，直接返回
    if (sum >= min) {
        return;
    }

    // 剩下的元素作为最后一个子集
    if (nset == m - 1) {
        uint64_t setsum = 0;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                setsum += arr[i];
            }
        }
        uint64_t total = sum + setsum * setsum;
        if (total < min) {
            min = total;
        }
        return;
    }

    // 生成下一个子集
    subset(0, 0, sum, nset);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%llu", &arr[i]);
    }

    // 降序排序数组：优先处理大元素，快速触发剪枝
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] < arr[j]) {
                uint64_t temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    find(0, 0);
    printf("%llu\n", min);
    return 0;
}

关键修改说明 #

1. 修正参数类型：将subset函数的sum参数改为uint64_t，确保大数值不会溢出。
2. 禁止空子集：在subset函数中，仅当subsum > 0时才进入下一轮划分，避免无效分支。
3. 降序排序数组：优先处理大元素，能更快找到接近最优的解，提前触发剪枝，大幅减少递归次数。
4. 重复元素剪枝：排序后，若当前元素与前一个元素相同且前一个未被选中，跳过当前不选的情况，避免重复计算相同的子集组合。

内容的提问来源于stack exchange，提问作者bruce