题解 | #数组分组#

import java.util.ArrayList;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];//sum所有数的和。
            if (nums[i] % 3 == 0) {
                    //3的倍数，直接舍弃   
                nums[i] = 0;
                // nums中只剩下5的倍数和其他数。
            }
        }
        if (sum % 2 != 0) {
            //和不是偶数，不能平均分成两组。直接打印 false
            System.out.println(false);
        }else{
            int halfOfSum = sum / 2;
                //使用nums数组能否组成 halfOfSum 
            System.out.println(dp(nums, 0, halfOfSum));
        }
    }

    /**
     * dp[startIndex:]能否拼凑出halfOfSum
     */
    private static boolean dp(int[] nums, int startIndex, int halfOfSum) {
        if (startIndex == nums.length) {
            if(halfOfSum == 0){
                return true;
            }else{
                return false;
            }
        }
        if (nums[startIndex] % 5 == 0) {
                //5的倍数，必须放在当前组。每次halfOfSum减去一个值，看能不能使得halfOfSum=0。
            return dp(nums, startIndex + 1, halfOfSum - nums[startIndex]);
        } else {
               //不是5的倍数,放在哪一组都可以。每次halfOfSum 减去一个值 或者 不减，看能不能使得halfOfSum=0。
            return dp(nums, startIndex + 1, halfOfSum) ||
                    dp(nums, startIndex + 1, halfOfSum - nums[startIndex]);
		  // 这里好厉害，居然可以这样返回
        }
    }
}