如果我知道，变量a，b，c，d，e可能有多少种组合：

a+b+c+d+e = 500

并且它们都是整数并且> = 0，所以我知道它们是有限的。

解决方案

回答

如果它们是实数，则为无穷大...否则，将有些棘手。

(好吧，对于任何用实数表示的计算机，它的计数都是有限的……但是那会很大！)

回答

解决问题的一种方法如下：

首先，a可以是0到500之间的任何值。然后，如果b + c + d + e = 500-a。这将问题减少了一个变量。递归直到完成。

例如，如果a为500，则b + c + d + e = 0，这意味着对于a = 500，只有b，c，d和e值的一种组合。

如果a为300，则b + c + d + e = 200，实际上与原始问题相同，只是减少了一个变量。

注意：正如克里斯指出的那样，这是实际尝试解决问题的可怕方法。

连结文字

回答

包括底片？无限的。

只包括正面？在这种情况下，它们将不被称为"整数"，而是被称为"自然"。在这种情况下...我真的不能解决这个问题，我希望可以，但是我的数学太生锈了。可能有一些疯狂的整体方法可以解决此问题。我可以为数学熟练的人提供一些指导。

是x的最终结果，
a的范围是从0到x，
b的范围是从0到(x a)，
c的范围是从0到(x a b)，
依此类推，直到e。

答案是所有这些可能性的总和。

我正在尝试在Google上找到一些更直接的公式，但是今天我对Google-Fu的评价确实很低...

回答

问题的答案是2656615626.

这是生成答案的代码：

public static long getNumCombinations( int summands, int sum )
{
    if ( summands <= 1 )
        return 1;
    long combos = 0;
    for ( int a = 0 ; a <= sum ; a++ )
        combos += getNumCombinations( summands-1, sum-a );
    return combos;
}

在情况下，" summands"为5，而" sum"为500。

请注意，此代码很慢。如果需要速度，请缓存来自" summand，sum"对的结果。

我假设我们想要数字"> = 0"。如果要使用"> 0"，则将循环初始化替换为" a = 1"，并将循环条件替换为" a <sum"。我也假设我们想要排列(例如1 + 2 + 3 + 4 + 5加2 + 1 + 3 + 4 + 5等)。如果需要a> = b> = c> = d> = e`，则可以更改for循环。

回答

几个月前，我为我父亲解决了这个问题...扩展供我们使用。这些往往是一次性的问题，所以我没有选择最可重用的...

a + b + c + d =总和

i =组合数

for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }

回答

@ Torlack，@ Jason Cohen：递归在这里不是一个好主意，因为存在"重叠的子问题"。就是说，如果我们选择a为1，b为2，那么剩下的3个变量的总和为497. 通过选择将" a"选择为" 2"，将" b"选择为" 1"，可以得出相同的子问题。 (这种巧合的数量随着数量的增长而爆炸。)

解决此类问题的传统方法是动态编程：从表底向上构建子问题的解决方案(从" 1个变量的多少组合加起来为0？"开始)，然后通过迭代进行构建(即" n个变量的多少组合加到k？"的解决方案是" n-1个变量的多少组合加到j？"的解决方案的总和，且0 <= j <= k。

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

回答

实际上，这是在面试中问的一个好问题，因为它很简单，我们可以在白板上写下，但又足够复杂，如果他们对问题的思考不够仔细，可能会使某人绊倒。同样，我们也可以为两个不同的答案提供不同的答案，这将导致实现方式完全不同。

订单事项
如果顺序很重要，那么任何解决方案都需要允许零出现在任何变量上；因此，最直接的解决方案如下：

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

返回2656615626.

顺序不重要
如果顺序无关紧要，那么解决方案就没有那么困难了，因为我们只需要确保不可能找到零就可以，除非已经找到总和。

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

传回2573155876.