题解 | #数组分组#

import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
/**
非常好理解的算法
利用回溯算法
sum = mod5（5的整倍数的和） + mod3（3的整倍数的和） + other（其他数的和）
target = sum/2
整理出来这些变量之后，接下来只要遍历other 在other列表里找到一个组合 使得
other + mod5 == target
或者
other + mod3 == target 即可
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();

        int sum = 0;
        int mod3 = 0;
        int mod5 = 0;
        ArrayList<Integer> other = new ArrayList<>();
        while (in.hasNextInt()) {
            // 注意 while 处理多个 case
            n = in.nextInt();
            if (n % 5 == 0) {
                mod5 += n;
            } else if (n % 3 == 0) {
                mod3 += n;
            } else {
                other.add(n);
            }
            sum += n;
        }

        if (sum % 2 != 0) {
            System.out.println(false);
        } else {
            System.out.println(trav(mod3, mod5, sum / 2, other, new boolean[other.size()],
                                    0, 0));
        }
    }

    // 回溯法
    private static boolean trav(int mod3, int mod5, int target,
                                ArrayList<Integer> nums, boolean[] used, int idx, int sum) {
        if (sum + mod3 == target) return true;
        if (sum + mod5 == target) return true;

        for (int i = idx; i < nums.size(); i++) {
            if (used[i] == false) {
                used[i] = true;
                if (trav(mod3, mod5, target, nums, used, i + 1, sum + nums.get(i))) {
                    return true;
                }
                used[i] = false;
            }
        }
        return false;
    }
}