题解 | #数组分组#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        // 将非5 非3 倍数的数字分为两组，使其差值为5和3组的差值
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum3 = 0, sum5 = 0, sum = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            sum += num;
            if (num % 5 == 0) {
                sum5 += num;
                continue;
            } else if (num % 3 == 0) {
                sum3 += num;
                continue;
            } else {
                list.add(num);
            }
        }

        if (sum % 2 != 0) {
            System.out.println("false");
            return;
        }
        int target = sum / 2 - sum5;


        if (list.size() == 0 && target == 0) {
            System.out.println("true");
            return;
        }

        if (list.size() == 1) {
            if (list.get(0) != target) {
                System.out.println("false");
            } else {
                System.out.println("true");
            }
            return;
        }

        int[] nums = new int[list.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = list.get(i);
        }
        // 组合，m个数据边选择x个数据(不可重复取)，使其和为target
        // 再次安排dfs
        for (int tag = 1; tag <= nums.length; tag++) {
            List<List<Integer>> arrange = new ArrayList<>();
            List<Integer> tmp = new ArrayList<>();
            boolean[] visited = new boolean[nums.length];
            dfs(arrange, tmp, nums, visited, tag, 0);
            for (List<Integer> tmpList : arrange) {
                int sumList = 0;
                for (Integer integer : tmpList) {
                    sumList += integer;
                    if (sumList == target) {
                        System.out.println("true");
                        return;
                    }
                }
            }
        }
        System.out.println("false");
    }

    /**
     * 因为需要选择x个数求和，因此只需要组合即可，不需要排列
     */
    public static void dfs(List<List<Integer>> arrange, List<Integer> tmp, int[] nums,
                           boolean[] visited, int tag, int cur) {
        if (tmp.size() == tag) {
            arrange.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = cur; i < nums.length; i++) {
            if (!visited[i]) {
                tmp.add(nums[i]);
                visited[i] = true;
                dfs(arrange, tmp, nums, visited, tag,i + 1);
                // 回溯
                visited[i] = false;
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}