# 12591 - The Power of Distributing
## 題解:
The Beauty of Distributing的測資加強版
有三個地方需要優化

**Optimization 1 :** 對reels進行由大到小的排序
**Optimization 2 :** 如果新的skill不能被剩下的填滿的話, 就回傳false
**Optimization 3 :** 如果ai超過box的話, 接下來一定不符合

## Code:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

int n, box; // n = total reel number, box = SUM / ans
int a[1000];
bool vis[1000];

int cmp(const void* a, const void* b){
    return *(int *)b - *(int *)a;
}

bool solver(int step, int sum) {
    if (step == n) return true;

    for (int i = 0; i < n; i++) {
        // Try to pick an unused reel to fill the current box
        if(vis[i])
            continue;
        // Case 1 : If sum < box after picking the reel
        // => Pick more reels to fill the current box by calling solver recursively
        vis[i] = true;
        if(sum + a[i] < box){
            if(solver(step + 1, sum + a[i]))
                return true;
        }
        // Case 2 : If sum == box after picking the reel
        // => Start with a new box (skill) by calling solver recursively with sum set to 0
        // => IMPORTANT : You can do Optimization 2 in this case after returning from solver
        else if(sum + a[i] == box){
            if(solver(step + 1, 0))
                return true;
            else
                return false;
        }
        vis[i] = false;
        // Optimization 3
        if (sum == 0) return false;
    }

    return false;
}

int main() {
    int T, SUM, ans; // SUM = sum of all reels, ans = total skill number

    scanf("%d", &T);

    while (T--) {
        // Read test case data
        SUM = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            SUM += a[i];
        }
        // Optimization 1
        qsort(a, n, sizeof(int), cmp);
        // Find the answer recursively and print the answer
        for (ans = n; ans > 1; ans--){
            if(SUM % ans != 0) // not integer
                continue;
            box = SUM / ans;
            memset(vis, false, sizeof(vis));
            if(solver(0, 0))
                break;
        }
        printf("%d\n", ans);
    }

    return 0;
}

###### tags: `NTHUOJ`