Generate all possible 3 positive integers that sum to N

Question

I am not good with math and I can't wrap my head around this, I want to generate EVERY possible 3 positive numbers there is that sum to N example 100, for instance:

0 - 0 - 100

0 - 1 - 99

1 - 1 - 98

You don't need to answer me with PHP code, just a general idea on how I can generate those numbers would be sufficient.

Thanks.

Answer 1

Brute force is an option in your case: you can just use 2 nested loops and it takes less than 10000 tests only.

  // pseudo code
  for (i = 0; i <= 100; ++i)
    for (j = 0; j <= 100; ++j) {
      if ((i + j) > 100)
        break;

      k = 100 - i - j;

      print(i, j, k); 
    } 

If duplicates e.g. 0, 0, 100 and 0, 100, 0 should be excluded, you can use slightly modified code:

  // pseudo code
  for (i = 0; i <= 100; ++i)
    for (j = i; j <= 100; ++j) {
      if ((i + j) > 100)
        break;

      k = 100 - i - j;

      if (j <= k)
        print(i, j, k); 
    } 

Answer 2

As for just an algorithm, consider first just pairs of numbers whose sum are less than or equal to 100. These should be easy to list. I.e

   0      1      2                 100
{{0,0}, {0,1}, {0,2},.........., {0,100}
               {1,1}, {1,2},..., {1,99}
 .
 .
 ...............................{50,50}}

But then each of those pairs, taking their sums can also be paired with precisely one number such that the entire triplet sum is 100.

So to summarize; if you could make first a list of these pairs (would require a double loop i in [0,100], j in [0:50]); and then loop through all pairs in this list calculating the third number you should get all triplets without duplication. Furthermore, if done correctly you wouldn't actually need any lists at all, with proper loop indexing you could calculate them in position.

edit Noticed you wanted duplicates - (though you could permute each triplet).

Answer 3

another approach with slightly better time complexity.

n=int(input())
for i in range(0,int(n/2+1)):
    for j in range(0,int(i/2+1)):
        print(j," ",i-j," ",(int)(n-i))
    l=n-i
    for j in range(0,int((n-i)/2+1)):
        print(j," ",l-j," ",(int)(i))

it is just the extension of this algorithm which produces two numbers whose sum is equal to n

n=int(input())
for i in range(0,int(n/2+1)):
    print(i," ",n-i)

I see you need those duplicates also just change the limits to full in line number 2,3 and 6

n=int(input())
for i in range(0,n):
    for j in range(0,i):
        print(j," ",i-j," ",(int)(n-i))
    l=n-i
    for j in range(0,l):
        print(j," ",l-j," ",(int)(i))