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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> // Function to print the contents of the given array void printCombination(int out[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", out[i]); printf("\n"); } // Recursive function to print all combination of numbers from i to n // having sum n. index denotes the next free slot in output array out void recurse(int i, int n, int out[], int index) { // if sum becomes n, print the combination if (n == 0) printCombination(out, index); int j; // start from previous element in the combination till n for (j = i; j <= n; j++) { // place current element at current index out[index] = j; // recurse with reduced sum recurse(j, n - j, out, index + 1); } } // main function int main(void) { int n = 5; int out[n]; // print all combination of numbers from 1 to n having sum n recurse(1, n, out, 0); return 0; } |

`Output:`

1 1 1 1 1

1 1 1 2

1 1 3

1 2 2

1 4

2 3

5

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <vector> using namespace std; // Function to print the contents of the given vector void printCombination(vector<int> const &out) { for (int i: out) cout << i << " "; cout << endl; } // Recursive function to print all combination of numbers // from i to n having sum n void recurse(int i, int n, vector<int> &out) { // if sum becomes n, print the combination if (n == 0) printCombination(out); // start from previous element in the combination till n for (int j = i; j <= n; j++) { // include current element from combination out.push_back(j); // recurse with reduced sum recurse(j, n - j, out); // backtrack - remove current element from combination out.pop_back(); } } // main function int main() { int n = 5; vector<int> out; // recurse all combination of numbers from 1 to n having sum n recurse(1, n, out); return 0; } |

`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. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

What about the case when repetitions are not allowed i.e, each number from the array may only be used

oncein the combination? How do we tweak the algorithm then?Thanks

https://ideone.com/GbQikT

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