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:

Output:

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

C++

Output:

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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Abhishek Sharma

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

Guest
Guest
Abhishek Sharma

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