每次分配一个苹果出去,然后再分配N-1个苹果。这里有个注意的地方就是,分那1个苹果的时候,假设还有N个苹果,不是从第一个人开始分,而是从N+1个苹果分配的位置开始,不然的话会产生重复的解。所以i=p不是i=0。
List<Integer> result = Lists.newArrayList(0, 0, 0);@Test/*** N个苹果 M个人分*/public void testMN() {foo(3, 3, 0);}private void foo(int n, int m, int p) {if (n == 0) {System.out.println(result);return;}for (int i=p; i<m; i++) {result.set(i, result.get(i) + 1);foo(n-1, m, i);result.set(i, result.get(i) - 1);}}
output
[3, 0, 0]
[2, 1, 0]
[2, 0, 1]
[1, 2, 0]
[1, 1, 1]
[1, 0, 2]
[0, 3, 0]
[0, 2, 1]
[0, 1, 2]
[0, 0, 3]