题解 | #数组分组#

参考别人的题解
先把三和五的倍数都挑出来，算好两边的和sum3和sum5，所有数总和为sum，不是3或5倍数的剩余的数放在集合中。
求出target = sum/2-sum3或者target=sum/2-sum5作为目标数，看list中找能不能凑出target。
在剩余集合中找target是一个dfs过程

• 终止条件，用完集合数，返回target==0

• 两种递归情况

• --选择start位置，递归找新目标数target-list.get(start)

• --不选择start位置，在start+1和以后位置找target
  特例：sum不是2的倍数，不可等分成两份，直接输出false

  import java.util.*;
  public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            //根据输入计算sum3，sum5和所有数总和sum，同时把不是5和3倍数的剩余数放入集合
            List<Integer> list = new LinkedList<>();
            int n = in.nextInt();
            int sum5=0, sum3=0, sum = 0;
            for (int i = 0; i < n; i++){
                int cur = in.nextInt();//输入
                if (cur % 5 == 0){//5倍数和
                    sum5 += cur;
                }else if (cur % 3 == 0){//3倍数和
                    sum3 += cur;
                }else{//剩余加入集合
                    list.add(cur);
                }
                sum += cur;//总和
            }
  
            //特例，总和不是2的倍数，不可分2份和相等的数字
            if(sum%2!=0) System.out.println("false");
            else{//否则，在剩余数中找目标数字
                int target = sum/2 - sum3;//也可以是sum/2-sum5
                System.out.println(helper(list, target, 0));
            }
        }
    }
  
    private static boolean helper(List<Integer> list, int target, int start){
        if (start == list.size()) return target == 0;//终止条件
  
        //选择start位置，递归找新目标数target-list.get(start)， 或者不选择start位置，在后面位置找target
        return helper(list, target-list.get(start), start+1) || helper(list, target, start+1);
    }
  }