N个苹果分给M个人，有多少种分法

每次分配一个苹果出去，然后再分配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]

巴特西

N个苹果分给M个人，有多少种分法

最新文章

热门文章