一个整数组，长度为 n，将其分为 m 份，使各的和相等求 m 的最大值，比如{3,2,4,3,6} 可以分成{3,2,4,3,6,} m=1;{3,6}{2,4,3}m=2 {3,3}{2,4}{6} m=3 所以m的最大值是3

 1 package number;
 2 
 3 /**
 4  * @author ycsun E-mail:stevesun521@gmail.com
 5  * @version 创建时间：2012-10-3 下午2:59:49 类说明
 6  */
 7 public class ArrayOperation {
 8     private int[] arr;
 9     private int[] aux;
10     private int groupid = 0;
11 
12     public ArrayOperation(int[] arr) {
13         this.arr = arr;
14         aux = new int[arr.length];
15     }
16 
17     /**
18      * @param int[] arr 一个整数组，长度为 n，将其分为 m 份，使各的和相等求 m 的最大值，比如{3,2,4,3,6}
19      *        可以分成{3,2,4,3,6,} m=1;{3,6}{2,4,3}m=2 {3,3}{2,4}{6} m=3 所以m的最大值是3
20      */
21     public int averageSplitArray() {
22         if (arr.length == 1) {
23             return 1;
24         }
25         int res = 1;
26         int sum = 0;
27         for (int i = 0; i < arr.length; i++)
28             sum += arr[i];
29         for (int i = 1; i < arr.length; i++) {
30             if (sum % i != 0)
31                 continue;
32             groupid = 0;
33             for (int j = 0; j < arr.length; j++)
34                 aux[j] = 0;
35             averageSplitArray(i,sum / i,sum/i);
36             int gnum = i;
37             if (gnum > 0) {
38                 System.out.println("gnum :" + gnum);
39                 for (int g = 1; g <= i; g++) {
40                     System.out.print("{");
41                     for (int k = 0; k < aux.length; k++) {
42                         if (aux[k] == g) {
43                             System.out.print(arr[k] + ",");
44                         }
45                     }
46                     System.out.println("}");
47                 }
48             }
49         }
50         return res;
51     }
52 
53     private boolean  averageSplitArray(int groupnum,int groupsum,int goalsum) {
54         if (goalsum == 0) {
55             groupid++;
56             goalsum=groupsum;
57             if (groupid == groupnum + 1)
58                 return true;
59         }
60         for (int i = 0; i < aux.length; i++) {
61             if (aux[i] != 0)
62                 continue;
63             aux[i] = groupid;
64             if(averageSplitArray(groupnum,groupsum,goalsum-arr[i])) return true;
65             aux[i]=0;
66         }
67         return false;
68     }
69 
70     public static void main(String[] args) {
71         int[] arr = { 3, 2, 4, 3, 6 };
72         ArrayOperation ao = new ArrayOperation(arr);
73         ao.averageSplitArray();
74     }
75 
76 }