题解 | #数组分组#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static ArrayList<Integer> list1 = new ArrayList<>();//存放5的整数倍
    public static ArrayList<Integer> list2 = new ArrayList<>();//存放3的整数倍 不包括5*3的公倍数
    public static ArrayList<Integer> list = new ArrayList<>(); //存放挑剩下的数字
    public static boolean[] visit; //剩余数字的使用状态，长度和list相同 false未使用 true已使用
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();//读取空格 不加这一步 下面读取的strArr就是空的
            String[] strArr = in.nextLine().split(" ");
            // 设一个变量 计算所有数字之和 如果数字之和为奇数 直接出false
            int sumAll = 0;
            //把数字装进 list1 list2 list里面
            for (int i = 0; i < n; i++) {
                int temp;
                temp = Integer.parseInt(strArr[i]);
                if (temp % 5 == 0) {
                    list1.add(temp);
                } else if (temp % 3 == 0) {
                    list2.add(temp);
                } else {
                    list.add(temp);
                }
                sumAll += temp;
            }

            if (sumAll % 2 != 0) {
                System.out.println(false);
                break;
            }

            //确定visit数组的长度
            int size = list.size();
            visit = new boolean[size];
            System.out.println(disver(0));
        }
    }
  
  //int index为目前已经使用的数字个数 当index和list数组的长度相同时，递归结束
    public static boolean disver(int index) {
        //正确的退出条件 已使用的数字个数等于list的size 并且两序列之和相等
        if (index == list.size() && sumArr(list1) == sumArr(list2)) {
            return true;
        }
        //进行选择：
        //第一步 在可用数字中选择一个 for循环+if（！visit[i]）用来依次选择全部可用的数
        //第二步 将这个数字放进list1或者list2中
        for (int i = 0; i < visit.length; i++) {
            if (!visit[i]) {
                //选择list里一个未被使用的数字 并把这个数字的使用状态设置为true
                int tempNum = list.get(i);
                visit[i] = true;//更改该数字的使用状态
                //之后有两种选择
                //第一种 添加到list1里
                list1.add(tempNum);
                if (disver(index + 1)) return true;
                //恢复现场
                list1.remove(list1.size() - 1);
                //第二种 添加到list2里
                list2.add(tempNum);
                if (disver(index + 1)) return true;
                //恢复现场
                list2.remove(list2.size() - 1);
                //两种选择结束，将选择的数字恢复到未使用状态
                visit[i] = false;
            }
        }
        return false;
    }
    public static int sumArr(ArrayList<Integer> list) {
        int sum = 0;
        for (int num : list) {
            sum += num;
        }
        return sum;
    }
}