题解 | #数组分组#

解题思路：递归，深搜

这个真的最后的再非3和非5的列表中查找多数之和是否存在和为target的可能。看了题解，睡前灵光一现才想通。期间考虑过01背包思想。

此题最主要解决的问题是 求列表中是否存在多数之和 = target目标题。
底层思维为：假设当前数是 target的一个加数，另一个是假设不是一个加数。一次在递归的时候，每次的下标后移，都会对应两种可能的目标值： target （当前数不当做加数，计算下一个数），或者 target-当前数（将当前数作为一个加数，找剩余的list数据中是否存在新的目标和）。下一轮递归的结果依旧会对应上述说的俩种情况，也就能够实现以下这种情景：
如target =10， list = 2，5，4，3；明显2+5+3=10；但是中间多了个4.
也就是当i走到3时，下标后移时，可以加4 求新目标值；也会走不加四，当时目标和不变下标+1。

import java.util.*;

import java.util.stream.Collectors;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(in.nextInt());
            }

            // 给定几个数组，5的倍数必须在一个数组，3的倍数必须在另一个数组，  其他的随意
            List<Integer> five = new ArrayList<>();
            List<Integer> three = new ArrayList<>();
            List<Integer> other = new ArrayList<>();

            for (int i = 0; i < list.size(); i++) {
                int value = list.get(i);
                if (value % 3 == 0) {
                    three.add(value);
                } else  if (value % 5 != 0) {
                    other.add(value);
                }
            }

            int threeSum = three.stream().mapToInt(Integer::intValue).sum();
            int sum = list.stream().mapToInt(Integer::intValue).sum();

            // 根据题意可以得出，在other列表中存在一个数字或者多个数字的和 为一下公式的值。
            // s5 + m = s3 + n;
            // (s5 + m) + (s3 + n) = sum;
            // 可以推出： n = sum/2 - s3;
            int t = sum / 2 - threeSum;

            if (sum % 2 != 0) {
                System.out.println(false);
            } else {
                //否则，在剩余数中找目标数字
                System.out.println(helper(other, t, 0));
            }
        }
    }

    private static boolean helper(List<Integer> list, int target, int start) {
        if (start == list.size()) return target == 0;//终止条件

        // 针对每一个数组，都有 求和=target   使用它和不使用它的情况 计算。    使用 即target不变，不实用则target-start的值。
        // 类似于01背包的思想
        return helper(list, target - list.get(start), start + 1) ||
               helper(list, target, start + 1);
    }



}

题解 | #数组分组#

解题思路： 递归，深搜

解题思路：递归，深搜