【花落&月缺】数组分组

题目来源及内容

	题目来源：牛客网-在线编程-华为机试-HJ093题目链接：[数组分组](https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86)题目内容：输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），能满足以上条件，输出true；不满足时输出false。

分析题目

题目中要求将数组分成两组，且满足以下两个要求：

1. 两组中各元素加起来的和相等，只要保证数组中所有元素的和是2的倍数即可；
2. 所有5的倍数必须在其中一组，所有3的倍数在另一组中，为达到这个目的，需要统计出原数组中所有非3且非5倍数的元素，并验证这些数字是否可以分为两组，分别放入3倍数和5倍数的两个数组中，使得这两个数组的元素和相同；

技巧处理

本题的难点在于如何解决题目中的要求2，现转换为另一种思路：
首先定义一些变量：

	int total3;// 数组中为3的倍数的元素的和int total5;// 数组中为5的倍数的元素的和List<Integer> list;// 用于存储原数组中不为3也不为5的元素

我们想要分为两组数组中的元素和相同，其实就是希望： list中的一些数字的和 + total3 = list中另一些数字的和 + total5; 即：
total3 - total5 = list中的一些数字的和 - list中另一些数字的和

上式中，等式的左侧很容易求，于是问题就转换为了穷举出等式的右侧的所有可能结果。
因为在数学计算中，加减法的计算顺序并不会影响计算结果，因此，我们可以用下列代码穷举出list中元素进行加和减运算的所有的值：

	List<Integer> list2 = new ArrayList<Integer>();// 记录所有可能的值list2.add(0);for (Integer otherNum : list) {List<Integer> list3 = new ArrayList<Integer>();for (Integer sum : list2) {list3.add(otherNum + sum);list3.add(otherNum - sum);}list2 = list3;list3 = new ArrayList<Integer>();}

代码解释：

1. 进行list2.add(0);即在对list中所有元素进行计算前，list中元素组合的值只有一个，即0；
2. 取出list中的一个元素otherNum，对list2中每一个元素进行一次加法计算和一次减法计算，并将结果存入到list3中；
3. 完成step2后，将list3赋值给list2，此时list2表示的是：包含otherNum在内，其在list中该元素之前的所有元素进行加法或减法的全部运算结果；
4. 清空list3后，返回第2步，直到list遍历结束。

求出所有可能的结果后，依次与total3 - total5的值进行对比即可。

代码实现

private boolean solution(int length, int[] nums) {int total = 0, total3 = 0, total5 = 0;List<Integer> list = new ArrayList<Integer>();for (int i = 0; i < length; i++) {total += nums[i];if (nums[i] % 5 == 0)total5 += nums[i];else if (nums[i] % 3 == 0)total3 += nums[i];elselist.add(nums[i]);}if (total % 2 != 0)return false;if (list.size() == 0 && total3 == total5)return true;else if (list.size() != 0 && total3 == total5)return false;else {List<Integer> list2 = new ArrayList<Integer>();list2.add(0);for (Integer otherNum : list) {List<Integer> list3 = new ArrayList<Integer>();for (Integer sum : list2) {list3.add(otherNum + sum);list3.add(otherNum - sum);}list2 = list3;list3 = new ArrayList<Integer>();}int temp = total3 - total5;for (Integer sum : list2) {if (sum == temp || sum == -temp)return true;}}return false;
}

——————附一张小姐姐给你打气，要继续加油呀！O(∩_∩)O————