鄙人近日看到一个算法题，觉得非常有趣，题目为：任意一些数字分为三组，使得每组之和尽量相等。题目看似简单，但是要设计出能够经得住不限数量、不限大小、不限顺序的任意数字的测试的算法并且写成代码实现，并不那么容易。 鄙人想了多种方法解决这个问题。

第一种是将任意数字分成3组的所有可能的组合全部求出存入集合，然后遍历集合找出和差距最小的3组的组合。这种方法不仅编码复杂，程序的计算量也太大。鄙人亲测，写出来后只能计算11个数字的分组，数字超过10个的话程序就卡死。

第二种是先将数组从小到大排序，然后取出最后一个数字成一个数组，再遍历剩下的数字，找到能加入该数组能使得新数组之和与均值的差距变得最小的那个数字，将其加入数组中。再使用递归找到下一个能加入新数组后使得新数组之和与均值的差距变得最小的数字然后加入数组……不断递归，直到找不到这样的数字为止，就完成了第一个数组的创建。再依次完成第二个和第三个数组。这种方法的计算量比第一种小很多，但是结果在多种数字测试下不总是准确。

第三种方法是鄙人最后想到的，也是最好的一种方法，不仅计算结果准确无误，而且计算量也不大，能够经得起大量数字的测试。本篇博客主要讲这种方法的算法和代码。具体为先计算这些数字之和并且除以3得到的值成为均值，再将这些数字任意分为三组。取出和最大的数组（下称较大数组）与和最小的数组 （下称较小数组），将其中的数字分别从小到大进行排序，计算这两个数组与均值的偏差之和，成为总偏差。通过双重for循环遍历这两个数组，较大数组在外部的for循环先取出一个数字，然后进行判断这个数字是否在在直接加入较小数组之后能让两个数组与均值的总偏差变小，可以的话则将其直接放入较小数组之中。这是第一种数字交换方法。如果第一种数字交换方法不能使得两数组与均值的总偏差变小的话，再进行下面的判断。从小到大遍历较小数组，依次取值，每次取值之后判断已经取出的所有数字是否可以与较大数组当前取出的数字进行交换，使得交换后两个数组之和与均值的总偏差变小。这是第二种交换方式。每次交换之后，使用递归方法进入下一轮的遍历与交换，并且结束后面的循环。 当较大数组与较小数组经过一次以上方法处理之后，判断两个数组是否有数字变化，有的话在新的数组中重新选取和最大与和最小的两个数组进行以上方法的遍历与交换。如果数组的数字没有变化，说明和最大与和最小的两个数组已经没有数字可以交换，能使得两数组之和离均值的偏差减小，这时候说明3个组合已经达到最佳状态。

1、计算数字的总和除以3的值，称为均值。将这些数字任意分为三组，并且按照从小到大的顺序进行排序。 2、从中取出和最大和最小两个数组，计算两组和与均值的总偏差。 3、遍历和最大的数组，依次取出数字后判断其是否其值是否比总偏差的1/2小，小的话直接将其赠给和最小的数组。 4、如果在第3步没有发现可以直接赠予的数字，遍历和最小的数组，将其中的数字从小到大开始累加，直到累加值可以与最大数组中的数字进行交换为止，即交换后使得两个数组与均值的总偏差变小。然后将最大数组中的数字和最小数组中的数字进行1对N交换。 5、每次交换完成后，结束当前循环，通过递归进入下一次寻找和交换。 6、如果一次方法运行结束后没有进行数字交换，则表示该两个数组已经达到最佳状态。 7、再次从得到的3个新的数组中取出和最大与和最小的两个组，使用递归来重新开始遍历和数字交换。 8、如果一轮遍历结束后，两个数组中的数字没有发生变化，则说明和最大的数组与和最小的数组已经没有数字可以交换，3个数组已经达到理想状态，即和尽量相等的状态。