题解 | #数组分组#

抄袭大佬

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            // 求数组所有元素总和
            int sum = 0;
            // 统计3倍数总和
            int sum3 = 0;
            // 统计5倍数总和
            int sum5 = 0;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int cur = sc.nextInt();
                if (cur % 3 == 0) {
                    sum3 += cur;
                } else if (cur % 5 == 0) {
                    sum5 += cur;
                } else {
                    list.add(cur);
                }
                sum += cur;
            }
            // 寻找其中一个数组减掉3的倍数元素之和后，剩余总和
            int target = sum / 2 - sum3;//也可以是sum/2-sum5
            if (sum % 2 != 0) {
                // 特例：sum不是2的倍数，不可等分成两份，直接输出false
                System.out.println(false);
            } else {
                System.out.println(canSplit(list, target));
            }
        }

    }

    private static boolean canSplit(List<Integer> list, int target) {
        return canSplit(0, list, target);
    }

    private static boolean canSplit(int start, List<Integer> list, int target) {
        // start等于集合大小，说明已遍历完
        if (start == list.size()) {
            // target==0说明递减元素值刚好达成目标值
            return target == 0;
        }
        //--选择start位置，递归找新目标数，余值减掉当前位置的元素值。target-list.get(start)
        //--不选择start位置，在start+1和以后位置找target，直接看下一个元素是否匹配
        return canSplit(start + 1, list, target - list.get(start)) || canSplit(start + 1, list, target);
    }
}