快速的方法来列出其中的数字之和所有可能的组合，一个常数 [英] fast method to list all possible combination of numbers which sum to a const number

问题描述

假设我们需要列出四个号A，B，C和D. A + B + C + D的总和是10和每个数字的值在范围[0，10]。

Assume we need to list four numbers A, B, C, and D. The sum of A+B+C+D is 10 and the value of each number is in the range of [0, 10].

查找所有可能的组合。

蛮力方法如下：

for (int A = 0; A <=10; ++A)
  for (int B = 0; B <=10-A; ++B)
  {
   if (A + B > 10) break;    
   for (int C = 0; C <=10-A-B; ++C)
   {
    if (A + B + C > 10) break;
    for (int D = 0; D <=10-A-B-C; ++D)
    {
       if (A + B + C + D == 10)
       {
         cout << "A: " << A << ",B: " << B << ",C: " << C << ",D: " << D << endl;
         break;
       }
       else if (A + B + C + D > 10)
         break;
    }
   }
  }

Q>有没有更好的解决办法？

Q> Is there a better solution?

FYI：code是根据建议更新从@rici

FYI: code is updated based on suggestion from @rici

推荐答案

什么是这样的：

void print4Partitions(int num) {
    for (int A=1; A<num-3; A++) {
        for (int B=A+1; B<num-A-2; B++) {
            for (int C=B+1; C<num-(A+B)-1; C++) {
                int D = num-A-B-C;
                printf("%d %d %d %d\n", A, B, C, D);
            }
        }
    }
}

这里的主要思路是：

The main ideas here are:

• 您真的没有需要循环的最后一个数字：它可以简单地计算，如@nci提到，如 A ， B ， C ，这个数字是分区唯一确定 D 。
• 您可以限制你的循环，而不是测试，并使用破发语句，这将导致更快的code。

• You really don't need to loop over the last number: it can be simply computed, as @nci mentions, as A, B, C, and the number to be partitions uniquely determine D.
• You can limit your loops instead of testing and using break statements, which should result in faster code.

这篇关于快速的方法来列出其中的数字之和所有可能的组合，一个常数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！