Print all combination of numbers from 1 to n having sum n

Given a positive integer n, print all combination of numbers from 1 to n having sum n.


 

For example,


For n = 5, below combinations are possible

{ 5 }
{ 1, 4 }
{ 2, 3 }
{ 1, 1, 3 }
{ 1, 2, 2 }
{ 1, 1, 1, 2 }
{ 1, 1, 1, 1, 1 }

 
For n = 4, below combinations are possible

{ 4 }
{ 1, 3 }
{ 2, 2 }
{ 1, 1, 2 }
{ 1, 1, 1, 1 }

 

 
We can use recursion to solve this problem. The idea is to consider every integer i from 1 to n and add it in the output and recurse for remaining elements [i..n] with reduced sum (n-i). To avoid printing permutations, each combination will be constructed in non-decreasing order. If combination of given sum is reached, we print it.

 
Below is C/C++ implementation of the idea:

C

Download   Run Code

Output:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

C++

Download   Run Code

Output:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek Sharma
Guest

What about the case when repetitions are not allowed i.e, each number from the array may only be used once in the combination? How do we tweak the algorithm then?

Thanks

Cody
Guest
Abhishek Sharma
Guest

@Cody: The answer is feasible in the current context when the array/vector contains all distinct elements from 1 to n. If we were given a vector of numbers, say [10, 2, 5, 8, 45, 2, 6], here the number 2 repeats, and we have to use it 2 times only since it’s present in the array two times. Here, the solution doesn’t work.