题解 | #数组分组#
数组分组
https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86
import java.util.Scanner; 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 num = in.nextInt(); List<Integer> list = new ArrayList(); while (in.hasNextInt()) { list.add(in.nextInt()); } List<Integer> left = new ArrayList(); List<Integer> right = new ArrayList(); int leftSum = 0, rightSum = 0, total = 0; for (Integer item : list) { if (item % 5 == 0) { left.add(item); leftSum += item; } if (item % 3 == 0) { right.add(item); rightSum += item; } total += item; }; // 左右高度差 int sum = Math.abs(rightSum) - Math.abs(leftSum) > 0 ? rightSum-leftSum: leftSum-rightSum; list.removeAll(left); list.removeAll(right); // 剩余列表中空的,则提前结束 if (sum == 0 && list.size() == 0) { System.out.println(true); return; } // 奇数不满足条件 if (total % 2 != 0) { System.out.println(false); return; } // 求t, leftSum+t+rightSum+t+sum = total int t = (total - leftSum - rightSum - sum) / 2; int remainSum = list.stream().mapToInt(i->i).sum(); // 是否存在 前i个元素内子集和为t System.out.println(search(list, t, list.size() - 1)); } } //是否存在 前i个元素内的子集和为t protected static boolean search(List<Integer> list, int target, int i) { if (target == 0) { return true; } if (i == 0) { return target == list.get(0) ; } // 不选择 第i个元素 或 选择 return search(list, target, i - 1) || search(list, target - list.get(i), i - 1); } }