N个整数加起来等于A的不同组合数量

Question

我想计算N个整数的不同有序组合数量，使得每个组合的元素总和为A。

例如，如果N = 3，A = 3，则结果应为10：
1 = [3, 0, 0]
2 = [2, 1, 0]
3 = [1, 2, 0]
4 = [0, 3, 0]
5 = [2, 0, 1]
6 = [1, 1, 1]
7 = [0, 2, 1]
8 = [1, 0, 2]
9 = [0, 1, 2]
10 = [0, 0, 3]

我使用的方法是暴力破解：

public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;

    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);

    return sum;
}

我怀疑可能有更好的方法（一些我没有想到的数学计算），是否存在？

编辑：在原问题中，我忘记考虑顺序。

- bennyl

Answer 1

这是将A进行组合分解为N份（包括零份）的方法。对于一组(A, N)，其组合数等于C(A + N - 1, A)，其中C()表示组合数，也称作二项式系数。可以在此处和此处查看相同的公式。

- MBo

Answer 2

想象一个长度为A的大片段。并想象N-1个有序的分隔符，将该片段分成若干部分。因此，每个部分都是一个加数，整个片段则是总和。

因此，您只需要提供一种算法来枚举分隔符的位置。

第一个分隔符可以放在任何N+1个位置之一，即P_0={0,1,...N}。

第二个分隔符可以放在任何的位置上。

以此类推。

您可以使用递归来实现这一点。

- Suzan Cioc

Answer 3

我相信有一个数学计算方法可以回答这个问题，但由于这是一个编程问答，我告诉你如何使你的程序更快地给出答案：你可以使用记忆化。

目前，你的程序每次都要重新计算calc(a, n)的答案。然而，答案可以计算一次，因为它在后续调用中不会改变。添加一个二维数组来存储calc(a,n)的结果，初始化为-1，并在计算之前使用它来查找结果，以节省大量时间重复计算相同的数字：

private static int[][] memo = new int[30][30];
static {
    for(int i = 0 ; i != 30 ; i++)
        for(int j = 0 ; j != 30 ; j++)
            memo[i][j] = -1;
}
public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;
    if (memo[a][n] > 0) return memo[a][n];
    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);
    return (memo[a][n] = sum);
}

- Sergey Kalinichenko

---

也被称为动态规划。 - starblue

记忆化是几种动态规划技术之一；称其为“动态规划”则不够具体。 - Sergey Kalinichenko

Answer 4

对于枚举：使用其他解决方案中给出的公式，效率要高得多。除非必须，否则永远不要生成完整的n个整数组合。它们具有难以处理的属性，特别是如果您只想将它们总和而不是生成它们。生成它们是另一个问题...

对于生成：使用无循环算法...有许多O（1）-每个格雷码序列结果。几乎没有限制整数组合的变化没有或可以有无循环算法。这类问题的许多算法都非常特定，但是存在许多现代无循环算法，可用于解决此特定问题。超级高效。 brute force从来不是解决此问题的方法，除非您拥有大量并行计算资源。 Google或Google Scholar尽在掌握！ :D

希望这有所帮助！

- Daniel

Answer 5

我找到了另一种解决方案，只使用递归而不需要分隔符：

public class App201210121604 {

public static Vector<int[]> split(int sum, int count) {

    if( sum < 0 ) {
        throw new IllegalArgumentException("Negative sum is not allowed");
    }

    Vector<int[]> ans = new Vector<int[]>();

    // "reserved" end of recursion
    if( count <= 0 ) {
        // nothing to do
    }

    // end of recursion
    else if( count == 1 ) {
        ans.add(new int[] {sum});
    }

    // body of recursion
    else {
        // for each first summand from 0 to summ
        for(int i=0; i<=sum; ++i) {

            // do a recursion to get the "tail"
            for(int[] tail : split(sum-i, count-1)) {

                int[] group = new int[count];
                group[0] = i;
                System.arraycopy(tail, 0, group, 1, count-1);

                ans.add(group);
            }
        }
    }

    return ans;
}

public static void main(String[] args) {

    Vector<int[]> ans = split(8, 4);

    for(int[] group : ans) {
        for(int i=0; i<group.length; ++i) {
            if( i>0 ) System.out.print("+");
            System.out.print(group[i]);
        }
        System.out.println("");
    }
}

}

- Suzan Cioc