题解 | #数组分组# dfs递归，借鉴大佬，注释详尽

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.hasNext()) {
            //数据个数
            int n = Integer.parseInt(sc.nextLine());
            int sum3 = 0;//3的倍数的和
            int sum5 = 0;//5的倍数的和
            int sumAll = 0;//总和
            //存放非3非5倍数的数
            List<Integer> list = new ArrayList<>();
            //数据
            for (int i = 0; i < n; i++) {
                int temp = sc.nextInt();
                //优先5的倍数
                if (temp % 5 == 0) {
                    sum5 += temp;
                } else if (temp % 3 == 0) {
                    sum3 += temp;
                } else {
                    list.add(temp);
                }
                sumAll += temp;
            }

            //如果总和不是2的倍数，不可能分为两个相等的数组
            if (sumAll % 2 != 0) {
                System.out.println("false");
            } else {
                //sum3 + sum5 + list = sumAll
                //sumAll/2 = sum5 + list1  = sum3 + list2
                //list = list1 + list2
                int target = sumAll / 2 - sum5;
                System.out.println(dfs(list,target,0));
            }
        }
    }

    //dfs寻找target
    public static boolean dfs(List<Integer> list, int target, int start) {
        //终止条件 target=0表示已经从list中取到一些值的和为target
        //如果已经遍历到list最后一个值，还没有将target归零，则返回false；不进入else中的start+1，会造成越界异常
        if (start == list.size()) {
            return target==0;
        }
        else {
            //递归，用当前值能算出来或用下一个值能算出来
            return dfs(list, target - list.get(start), start + 1) || dfs(list,target,start+1);
        }
    }
}