# Given a number $N$ and two numbers lower than $N$, what are all of the combinations of those numbers that sum to $N$?

I tried looking around the website for a while but I was unable to find anything that matched this problems specifically. So if someone here knows of a question that is the same as mine, please link it.

If N is equal to 5 then we can use a set such as {1, 2, 3}.

If we wanted to know all ways in which {1, 2} can equal to 5, we get 1+1+1+2 and 1+2+2. So for the two numbers {1,2} there are two ways in which we can sum them up to equal 5. Using {2,3} the only way we can make 5 is 2+3. So there is one way in which we can sum those numbers to make 5.

So there is there an elegant way to find all the ways two numbers can sum up to a given number? In terms of a formula or algorithm, rather than just figuring them all out yourself.

Thanks.

• These are called "Integer partitions." See innumerable books or web pages on this. – David G. Stork Apr 7 at 1:24
• @DavidG.Stork I had a look at integer partitions, but I thought those were for every number lower than N. I'm looking for only two specific numbers, not every number lower than 5. – SJMcMullan Apr 7 at 1:34

Many software systems have this functionality, such as Mathematica.

An interesting application is to find out how you can get \\$1.56 in just pennies (1), nickels (5), dimes (10) and quarters (25):

IntegerPartitions[156, 10, {1, 5, 10, 25}]

(Find partitions of 156 up to length 10 "coins" consisting just of coins of value 1, 5, 10 and 25.)

Three ways:

{{25, 25, 25, 25, 25, 25, 5, 1},

{25, 25, 25, 25, 25, 10, 10, 10, 1},

{25, 25, 25, 25, 25, 10, 10, 5, 5, 1}}