# 12584 - The Beauty of Distributing
## 題意:
分配所有的數字成幾組, 每組的和都相同, 求最多幾組?
## 題解:
因為每組的和相同, 所以每組的和應該為sum/k
sum = 數字總和, k = 組的數量
Best case: k = n, Worst case: k = 1
用迴圈去測試k, 如果sum/k不是整數就跳過
測試的方法用DFS, 如果使用完所有卷軸就回傳TRUE
## Code:

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

int t, n, a[15];
int level, vis[15];

int dfs(int number, int sum){
    if(number == n) // used all the reels
        return 1;
    for (int i = 0; i < n; i++){
        if(vis[i])
            continue;
        vis[i] = 1;
        if(sum + a[i] < level){
        // continue with current skill
            if(dfs(number + 1, sum + a[i]))
                return 1;
        }
        else if(sum + a[i] == level){
        // start with new skill
            if(dfs(number + 1, 0))
                return 1;
        }
        vis[i] = 0;
    }
    return 0;
}

int main(){
    scanf("%d", &t);
    while(t--){
        int sum = 0, ans = 1;
        scanf("%d", &n);
        for (int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            sum += a[i];
        }
        for (int i = n; i > 1; i--){
            if(sum % i != 0) // level is not integer
                continue;
            level = sum / i;
            memset(vis, 0, sizeof(vis));
            if(dfs(0, 0)){
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

###### tags: `NTHUOJ`