题解 | #数组分组#

经典分割数组，组合问题，可以使用回溯

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 当前回溯的总和，相当于path
    public static int nowsum = 0;
    // 记录是否有满足条件的，有则为true
    public static boolean flag = false;
    // othersum记录额外组的总和
    public static int othersum = 0;


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int nums = Integer.parseInt(in.nextLine());
        String[] arrString = in.nextLine().split(" ");
        List<Integer> othergrou = new ArrayList<>();
        int sum = 0;
        int fivesum = 0;
        int threesum = 0;
        for (int i = 0; i < nums; i++) {
            int temp = Integer.parseInt(arrString[i]);
            // 计算数组总和
            sum += temp;
            // 计算5的组的总和
            if (temp % 5 == 0) {
                fivesum += temp;
            }
            // 计算3的组的总和
            else if(temp % 3 == 0) {
                threesum += temp;  
            } 
            // 记录其他的数
            else {
                othergrou.add(temp);
            }
        }
        // 如果数组总和为奇数，不能平分
        if (sum % 2 == 1) {
            System.out.println("false");
            return;
        } 
        // 计算3组和5组的差值绝对值
        int re = Math.abs(fivesum - threesum);
        // 计算其他组的总和
        othersum = sum-fivesum-threesum;
        // 回溯搜索是否有符合的子数组
        backtracking(othergrou, re, 0);
        // 有满足条件的记录，则返回true
        if (flag) {
            System.out.println("true");
            return;
        }
        System.out.println("false");
        
    }

    public static void backtracking(List<Integer> list, int target, int startIndex) {
        // 如果当前分组 g1 的nowsum - (othersum - nowsum) 等于五组和三组的和差值，就说明找到了合适的子数组
        if (Math.abs(2*nowsum - othersum) == target) {
            flag = true;
            return ;
        }
        // 回溯搜索
        for(int i = startIndex; i < list.size(); i++) {
            nowsum += list.get(i);
            backtracking(list, target, i+1);
            nowsum -= list.get(i);
        }
    }
}