题解 | #数组分组#

// 思路还是很直观的，分别将 5 的倍数和 3 的倍数分成两堆，然后计算二者的差值，如果剩下的数 d集合 能够有一个子集 dd 填满这个差值，
// 填满后剩下的 d 的子集 d-dd 中需要能够组成两个完全相等的数，让他们分别放到两个堆中，这样两个堆就一样大，即两个加和一样的分组。
// 关键的步骤是查找在集合 d-dd 中，是否存在若干个数能够组成 (sum-diff)/2 这个 target，如果存在的话那么就 true，否则 false。
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] inputs = br.readLine().trim().split(" ");
        ArrayList<Integer> a = new ArrayList<>();
        int fiveG = 0, threeG = 0;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int x = Integer.parseInt(inputs[i]);
            if (x % 5 == 0) {
                fiveG += x;
            } else if (x % 3 == 0) {
                threeG += x;
            } else {
                a.add(x);
                sum += x;
            }
        }
        
        int[] d = new int[a.size()];
        for (int i = 0; i < d.length; ++i) d[i] = a.get(i);
        int diff = Math.abs(fiveG-threeG);
        boolean res = true;
        if ((sum-diff) % 2 != 0 || findSumX(d, 0, (sum-diff)/2) == false)
            res = false;
        
        System.out.println(res);
        
    }
    
    public static boolean findSumX(int[] d, int cur, int x) {
        if (x == 0) return true;
        if (cur == d.length) return false;
        if (findSumX(d, cur+1, x-d[cur]) || findSumX(d, cur+1, x))
            return true;
        return false;
    }

}