题解 | 数组分组

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int n;
int c[30];
bool found = false;
// index: 当前处理的自由数字索引
// sum_a: a组当前和
// sum_b: b组当前和
// free_nums: 自由数字数组
// free_count: 自由数字个数
void dfs(int index, long long sum_a, long long sum_b, int free_nums[], int free_count) 
{
    if (found) return; // 如果已找到解，直接返回
    if (index == free_count) 
    { // 所有自由数字已分配完
        if (sum_a == sum_b) 
        {
            found = true;
        }
        return;
    }
    // 将当前自由数字加入a组
    dfs(index + 1, sum_a + free_nums[index], sum_b, free_nums, free_count);
    // 将当前自由数字加入b组
    dfs(index + 1, sum_a, sum_b + free_nums[index], free_nums, free_count);
}
int main() 
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &c[i]);
    }
    long long sum_a = 0, sum_b = 0;
    int free_nums[30];
    int free_count = 0;
    // 首先处理必须分配的数字
    for (int i = 0; i < n; i++) 
    {
        if (c[i] % 5 == 0) 
        {
            // 5的倍数必须加入a组
            sum_a += c[i];
        } else if (c[i] % 3 == 0 && c[i] % 5 != 0) 
        {
            // 3的倍数且不是5的倍数必须加入b组
            sum_b += c[i];
        } 
        else 
        {
            // 其他数字为自由数字
            free_nums[free_count++] = c[i];
        }
    }
    // 使用DFS尝试所有自由数字的分配方案
    dfs(0, sum_a, sum_b, free_nums, free_count);
    // 输出结果
    printf("%s\n", found ? "true" : "false");
    return 0;
}