题解 | #数组分组#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String a;
		char[] charAy;
		int[] number, grouped;
		int i = 0, l, n = 0, sum1 = 0, sum2 = 0, cnt = 0;
		try {
			a = in.readLine();
			l = a.length();
			charAy = new char[l];
			a.getChars(0, l, charAy, 0);
			while (i < l) {
				n *= 10;
				n += charAy[i] - '0';
				i++;
			}
			number = new int[n];
			grouped = new int[n];
			a = in.readLine();
			parse(a, number);
		} catch (IOException e) {
			e.printStackTrace();
			throw new RuntimeException(e);
		}
		i = 0;
		while (i < n) {
			if (number[i] % 5 == 0) {
				sum1 += number[i];
			} else if (number[i] % 3 == 0) {
				sum2 += number[i];
			} else {
				grouped[cnt++] = number[i];
			}
			i++;
		}
		//将第一个数组和第二个数组的差值作为是否可分组的依据
		//1:a+b+c+d=sum  令a-b=k  如果c-d=k  则两式相减a-b-(c-d)=0
		//得2:a-b-c+d=0  联立1式可得2a+2d=sum  所以a+d=sum/2  b+c=sum/2
		//a,d分为一组，b,c分为一组
		//sum1相当于a，sum2相当于b，sum1-sum2相当于k，
		//现只要求剩余的grouped数组中的数能分成+(g1+g2+..)-(g3+g4+..)=k的型式，即可以分组
		if (group(grouped, cnt, 0, sum1 - sum2))
			System.out.print(true);
		else
			System.out.print(false);
		try {
			in.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void parse(String a, int[] number) {
		int i = 0, j = 0, l = a.length(), t = 0;
		char[] charAy = new char[l];
		boolean negative = false;
		a.getChars(0, l, charAy, 0);
		while (i < l) {
			if (charAy[i] == ' ') {
				if (negative)
					t = -t;
				number[j++] = t;
				t = 0;
				negative = false;
			} else if (charAy[i] == '-') {
				negative = true;
			} else {
				t *= 10;
				t += charAy[i] - '0';
				if (i == l - 1) {
					if (negative)
						t = -t;
					number[j++] = t;
				}
			}
			i++;
		}
	}

	/**
	 * 
	 * @param grouped
	 * @param cnt
	 * @param div
	 * @param div0
	 * @return
	 */
	public static boolean group(int[] grouped, int cnt, int div, int k) {
		boolean groupable = false;
		if (cnt == 0) {
			groupable = div == k;
		} else {
			groupable = group(grouped, cnt - 1, div + grouped[cnt - 1], k);
			groupable = groupable
					|| group(grouped, cnt - 1, div - grouped[cnt - 1], k);
		}
		return groupable;
	}
}