定义：
木棒： 未被剪切
木棍： 被剪切后

剪枝：

1. 按木棒长度从小到大枚举，且只有sum % len == 0 时， 长度才是有效的

2. 优化搜索顺序， 减少分支， 从大到小枚举

3. 排除等效冗余
   3-1 按照组合数方式枚举
   3-2 如果当前木棍加到当前木棒中失败了， 则直接跳过后面所有长度相等的木棍
   3-3 如果木棒的第一根木棍失败， 则一定失败
   3-4 如果木棒的最后一根木棍失败， 则一定失败.

反正法证明

• 3-3证明

  首先， 同一根木棒里的木棍的位置可以任意交换而不影响结果
  反证法，假设第一根木棍长度为3， 失败了， 放到后面去成功了。
  放在第一根的长度为3的地方假设由两个木棍替代了。
  如果3放在同一根木棒， 交换位置3到第一根， 矛盾。
  如果3放在后面的木棒， 可以把3交换到木棒的最前面， 然后交换两个木棒的位置，矛盾。

• 3-4证明
  反正法， 假设最后一根木棍长度为3， 失败了， 放到后面的木棒成功了。
  那么这个位置3可能由其他的几根木棍代替， 这几根木棍和恰好为3， 直接交换下位置，矛盾。

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 70, sum, len, n;
    static int[] a;
    static boolean[] st;

    public static void main(String[] args) throws Exception{
        while(true){
            n = Integer.valueOf(read.readLine());
            if(n == 0) break;
            a = new int[n];
            st = new boolean[N];
            sum = 0; len = 1;
            String[] ss = read.readLine().split(" ");
            for(int i = 0; i < n; i++){
                a[i] = Integer.valueOf(ss[i]);
                sum += a[i];
            }
            //剪枝2. 优化搜索顺序， 减少分支， 从大到小枚举
            Arrays.sort(a);
            reverse(a);
            for(; len <= sum; len++){
                //剪枝1. 按木棒长度从小到大枚举，且只有sum % len == 0 时， 长度才是有效的
                if(sum % len == 0 && dfs(0, 0, 0)){
                    System.out.println(len);
                    break;
                }
            }
        }
    }

    public static boolean dfs(int group, int curLen, int start){
        if(group * len == sum)  return true;
        if(curLen == len) return dfs(group + 1, 0, 0);
        //剪枝3-1 按照组合数方式枚举
        for(int i = start; i < n; i++){
            if(st[i]) continue;
            if(curLen + a[i] > len) continue;

            st[i] = true;
            if(dfs(group, curLen + a[i], i + 1)) return true;
            st[i] = false;

            //剪枝3-3 如果木棒的第一根木棍失败， 则一定失败
            if(curLen == 0) return false;

            //3-4 如果木棒的最后一根木棍失败， 则一定失败
            if(curLen + a[i] == len) return false;

            //剪枝3-2 如果当前木棍加到当前木棒中失败了， 则直接跳过后面所有长度相等的木棍
            int j = i;
            while(j < n && a[j] == a[i]) j++;
            i = j - 1;
        }
        return false;
    }

    public static void reverse(int[] a){
        int l = 0, r = a.length - 1;
        while(l < r) {
            int tmp = a[l];
            a[l++] = a[r];
            a[r--] = tmp;
        }
    }

}