仿人通过的1011

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main();
	}

	int count;// 数字个数

	int[] a;
	boolean[] b;

	int L;// 当前匹配长度

	public Main() {
		Scanner s = new Scanner(System.in);
		while (s.hasNextInt()) {
			count = s.nextInt();
			if (count == 0) {
				break;
			}

			a = new int[count];
			b = new boolean[count];

			int sum = 0;
			for (int i = 0; i < count; i++) {
				int num = s.nextInt();
				sum += num;
				a[i] = num;
			}
			Arrays.sort(a);

			int max = a[count - 1];

			// 遍历可能的匹配长度
			for (int i : getList(sum)) {
				if (max <= i) {
					L = i;
					if (exec(count - 1, i, sum)) {
						System.out.println(i);
						break;
					}
				}
			}

		}

		s.close();

	}

	public boolean exec(int begin, int left, int all) {
		if (left == 0) {
			all -= L;
			if (all == 0) {
				return true;
			} else {
				left = L;
				begin = count - 2;// 从第二个数开始继续匹配，其实可以从第一个可用数开始匹配
			}
		}
		while (begin >= 0) {
			if (!b[begin]) {// 可用
				int n = a[begin];
				if (n <= left) {// 未过界
					b[begin] = true;// 假设使用了
					if (exec(begin - 1, left - n, all)) {
						return true;
					} else {
						b[begin] = false;// 还原
						if (left == L || left == n) {// 如果是首个或末个长度匹配失败，直接退出
							break;
						}
					}
				}
				while (--begin >= 0 && a[begin] == n) {// 下一个不同的数

				}
				int tleft = left;// 剩余之和是否足够
				for (int j = begin; j >= 0; j--) {
					if (!b[j]) {
						tleft -= a[j];
						if (tleft <= 0) {
							break;
						}
					}
				}
				if (tleft > 0) {
					break;
				}
			} else {
				begin--;
			}
		}

		return false;
	}

	// 获得所有因子，从小到大排序
	public List<Integer> getList(int n) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				list.add(i);
				if (i * i != n) {
					list.add(n / i);
				}
			}
		}
		Collections.sort(list);
		return list;
	}
}

 

http://blog.csdn.net/night_blue/archive/2008/09/23/2966056.aspx

比原作者的代码慢100毫秒多