题解 | #数组分组#

import java.util.Scanner;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
** 思路: 将输入的数字分成两组并且相等，每组为sum/2; 这样考虑的话会在等于0的时候有特殊判断:
	(1)当前递归成立的结果是否为空，如果为空，剩下的数字中是否是15的倍数
	(2)当前递归成立的结果结果满足要求，剩下的数组是否满足要求。
	(3)这里可以通过求乘积的方法。也可以选择计数统计的方法。
	(4)这道题上来没有想到3倍数一组 5 倍数这样的分组方法。所以，就在上面的思路进行了优化。
	(5) 利用一个小的字典dict_cnt_flag:dict_cnt_flag[0]表示3倍数的个数，dict_cnt_flag[1]表示5倍数的个数，dict_cnt_flag[2]表示当前求的数组是否存在3的倍数，dict_cnt_flag[3]表示当前求的数组是否是5的倍数。
	(6)每次递归的时候对dict_cnt_flag[2] 和 dict_cnt_flag[3]进行判断，如果当前结果集存在3或5的倍数，并且新进来的数字是3或者5的倍数时候，新进来的数字就不再添加。如果新进来3或5的倍数时，把对应标志为修改为3 和 5.
	(7)每次回溯的时候弹出stack(stack用来判断满足条件的最终结果是否为空)，如果加入的数字是3或5的倍数回溯的时候修改为0.
***/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException {
//    Scanner in = new Scanner(System.in);
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    String input;
    while ((input = read.readLine()) != null){
      int len = Integer.parseInt(input);
      int[] nums = new int[len];
      String[] strnums = read.readLine().split(" ");
      int[] visited = new
          int[len]; //如果是5的倍数放入了标记5， 如果是3的倍数放入标记3，其他1
      int total = 0;
      int[] dict_cnt_flag = new int[4];
      for (int i = 0; i < len; i++) {
        nums[i] = Integer.parseInt(strnums[i]);
        total += nums[i];
        if(nums[i] != 0){
          if(nums[i] % 3 == 0){
            dict_cnt_flag[0]++;
          }
          if(nums[i] % 5 == 0){
            dict_cnt_flag[1]++;
          }
        }
      }
      if (Math.abs(total) % 2 != 0) {
        System.out.println("false");
      } else {
        int target = total / 2;
        Stack<Integer> stack = new Stack<>();
        boolean ans = dfs(nums, 0, 0, target, visited, stack, dict_cnt_flag);
        System.out.println(ans==true ? "true" : "false");

      }
    }
  }

  public static boolean dfs(int[] nums, int index, int tmp, int target,
                            int[] visited, Stack<Integer> stack,int[] dict_cnt) {
    if (index >= nums.length && target == tmp) {
      if(stack.isEmpty()){
        return (dict_cnt[0] > 0 && dict_cnt[1] > 0) ? false : true;
      } else {
        int cnt_3 = dict_cnt[0];
        int cnt_5 = dict_cnt[1];
        return (cnt_3 > 0 && cnt_5 > 0) ? false : true;
      }
    }  else if (index >= nums.length && target != tmp) {
      return false;
    }

    boolean p1 = false, p2 = false, p3 = false, p4 = false;
    if ((nums[index] % 5 == 0 && dict_cnt[2] == 3)) {
      visited[index] = 1;
      p1 = dfs(nums, index + 1, tmp, target, visited, stack,dict_cnt);
    } else if (nums[index] % 3 == 0 && dict_cnt[3] == 5) {
      visited[index] = 1;
      p2 = dfs(nums, index + 1, tmp, target, visited, stack,dict_cnt);
    } else {
      visited[index] = 1;
      p3 = dfs(nums, index + 1, tmp, target, visited, stack,dict_cnt);
      stack.push(nums[index]);
      if(nums[index] % 3 == 0 ){
        dict_cnt[0]--;
        dict_cnt[2] = 3;
      } else if(nums[index] % 5 == 0){
        dict_cnt[1]--;
        dict_cnt[3] = 5;
      }
      p4 = dfs(nums, index + 1, tmp + nums[index], target, visited, stack, dict_cnt);
      int pop = stack.pop();
      if(pop % 3 == 0 ){
        dict_cnt[0]++;
        dict_cnt[2] = 0;
      } else if(pop % 5 == 0){
        dict_cnt[1]++;
        dict_cnt[3] = 0;
      }
    }
    visited[index] = 0;
    return p1 || p2 || p3 || p4;
  }


}