2

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].

Find all the possible combination.

The brute-force way is as follows:

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> Is there a better solution?

FYI: code is updated based on suggestion from @rici

q0987
  • 34,938
  • 69
  • 242
  • 387
  • 1
    Does 7,1,1,1 count or do the numbers need to be unique? Is 1,2,3,4 considered same as 2,1,3,4 or no? Perhaps it doesn't matter? – angelatlarge Mar 14 '13 at 01:53
  • 1
    The phrase to search for is "integer partition" (or "composition" if you care about order.) Most definitions exclude zeros but that's easy enough to work around. – DSM Mar 14 '13 at 02:01
  • 2
    for a start, it should be obvious that you can replace `for (int D = 0; D <=10; ++D) { if (A + B + C + D == 10)` with `D = 10 - (A + B + C)` at a considerable saving of time. – rici Mar 14 '13 at 02:01
  • order does matter since the sequence is for [A, B, C, D]. – q0987 Mar 14 '13 at 02:11
  • @q: you don't need those `if` statements since they mirror the condition in the preceding `for` statement. And you still needlessly iterate `D` from `0` until it reaches the only possible value. But you're almost there. – rici Mar 14 '13 at 02:31
  • I think this answer in Haskell, based on another SO answer, might be one possible solution (this case would be `partitions 10 4`) See here: http://stackoverflow.com/questions/15388241/algorithm-to-partition-distribute-sum-between-buckets-in-all-unique-ways/15390241#15390241 – גלעד ברקן Mar 14 '13 at 05:27

2 Answers2

0

You are asking for a method to enumerate the partitions of an integer. The linked wikipedia page lays out a few ways of doing that.

phs
  • 10,687
  • 4
  • 58
  • 84
0

What about something like this:

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:

  • 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.
angelatlarge
  • 4,086
  • 2
  • 19
  • 36
  • As far as I can tell, this code would only ever give {1 2 3 4}, since it doesn't allow repeated numbers, eg {2 2 2 4}. You're also assuming that order doesn't matter, eg {1 3 2 4}, where the OP said it did(in a comment). The bulleted points are good, though. – Geobits Mar 14 '13 at 18:29