题解 | #数据分类处理#

算法渣渣，不会递归、动态规划，突然发现与称砝码那道题思路一样

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            boolean b = test(arr);
            System.out.println(b);
        }
    }


    public static boolean test(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();//存放除了5的倍数和3的倍数之外的数
        int sum1 = 0;//5的倍数总和
        int sum2 = 0;//3的倍数总和（不包括5的倍数）
        int sum = 0;
        for (int j : arr) {
            sum += j;
            if (j % 5 == 0) {
                sum1 += j;
            } else if (j % 3 == 0) {
                sum2 += j;
            } else {
                list.add(j);
            }
        }
        if (sum % 2 != 0) { //总和为奇数，不能分组
            return false;
        } else {
            int mid = sum / 2;
            //在list集合中找出任意个数相加的结果，保存到set集合中（去重）
            //类似于称砝码那道题
            HashSet<Integer> hashSet = new HashSet<>();
            hashSet.add(0);
            for (Integer value : list) {
                ArrayList<Integer> temp = new ArrayList<>(hashSet); //保存上一次累加的结果
                for (Integer integer : temp) {
                    hashSet.add(integer + value);
                }
            }
            //如果有一个数与sum1（或sum2）相加等于总和一半，即可以分组
            for (Integer integer : hashSet) {
                if (integer + sum1 == mid) {
                    return true;
                }
            }
            return false;
        }
    }
}