题解 | #数组分组#

目标和问题的变种，通过一定的转化之后就变成在数组中寻找目标大小的子数组，然后想使用动态规划来解决的，可是因为元素中存在小于0的数，动态规划变得不适用 于是改用递归解决了(在题解中copy了一份，加了注释)

/**
首先判断数据和是不是偶数
将所有三的倍数放在一起，五的倍数放在一起
然后问题就是将剩下的数分成两组，两组差是多少，
接着就变成剩下的数中找到和为多少的，存在小于0的数，所以使用动态规划不行
*/

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = scanner.nextInt();
        }
        int sum3 = 0;
        int sum5 = 0;
        int sum = 0;
        int n35 = 0;
        for(int i = 0; i < n; i++){
            if(arr[i] % 5 == 0){
                sum5 += arr[i]; //所有5的倍数累加起来
                n35++;
            }else if(arr[i] %3 == 0){
                sum3 += arr[i]; //所有3的倍数(不包含5的倍数)累加起来
                n35++;
            }
            sum += arr[i];
        }
        if(sum % 2 != 0){
            System.out.println(false); //如果数据和不能平分，直接返回false
            return;
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(arr[i] % 3 != 0 && arr[i] % 5 != 0){
                list.add(arr[i]);
            }
        }
        // 如果数据和能够平分，如果需要满则条件，则在除去3，5的倍数的数中，应该能找到和为
        // sum / 2 - sum3的组合
        // sum / 2 - sum5的组合
        int target = sum / 2 - sum3;
        // 因为存在nums中存在数小于0，所以无法直接使用动态规划进行解决
        // 因此这边使用递归进行解决
        System.out.println(canPartition(list, target));
//         // 目标和问题 在arr_new中寻找目标和
//         boolean[][] dp = new boolean[n_new][target + 1];
//         // 使用dp[i][j]表示在arr_new[0:i]中是否存在和为j的组合
//         //先确定边界,存在负数
//         //dp[0][j]
//         for(int j = 0; j <= target; j++){
//             if(j == arr_new[0]){
//                 dp[0][j] = true;
//             }
//         }
//         for(int i = 1; i < n_new; i++){
//             for(int j = 0; j <= target ; j++){
//                 if(j >= arr_new[i]){
//                     dp[i][j] = dp[i][j - arr_new[i]] | dp[i - 1][j];
//                 }else{
//                     dp[i][j] = dp[i - 1][j];
//                 }
//             }
//         }
//         System.out.println(dp[n_new - 1][target]);
    }
    
    private static boolean canPartition(List<Integer> list, int target){
        // 从list中第0个元素开始选择
        return doCanPartition(0, list, target);
    }
    
    private static boolean doCanPartition(int index, List<Integer> list, int target){
        if(index == list.size()){
            return target == 0;
        }
        // 对list中第index个元素进行处理
        // 第index个元素可能会被选择，也可能不被选择，分两种情况
        // 递归的结束条件是遍历到列表的最后一个元素
        return doCanPartition(index + 1, list ,target - list.get(index)) | doCanPartition(index + 1, list ,target);
    }
}