Print all combinations of numbers from 1 to `n` having sum `n`
Given a positive integer n, print all combinations of numbers between 1 and n having sum n.
For example,
{ 5 }
{ 1, 4 }
{ 2, 3 }
{ 1, 1, 3 }
{ 1, 2, 2 }
{ 1, 1, 1, 2 }
{ 1, 1, 1, 1, 1 }
For n = 4, the following 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 to the output and recur for remaining elements [i…n] with reduced sum n-i. To avoid printing permutations, each combination will be constructed in non-decreasing order. If a combination with the given sum is reached, print it.
Following is the C, C++, Java, and Python 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 |
#include <stdio.h> // Function to print the contents of a given array void printCombination(int out[], int n) { for (int i = 0; i < n; i++) { printf("%d ", out[i]); } printf("\n"); } // Recursive function to print all combinations of numbers from `i` to `n` // having sum `n`. The `index` denotes the next free slot in the output array `out` void printCombinations(int i, int n, int out[], int index) { // if the sum becomes `n`, print the combination if (n == 0) { printCombination(out, index); } // start from the previous element in the combination till `n` for (int j = i; j <= n; j++) { // place current element at the current index out[index] = j; // recur with a reduced sum printCombinations(j, n - j, out, index + 1); } } int main(void) { int n = 5; int out[n]; // print all combinations of numbers from 1 to `n` having sum `n` printCombinations(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 a given array void printCombination(vector<int> const &out) { for (int i: out) { cout << i << " "; } cout << endl; } // Recursive function to print all combinations of numbers // from `i` to `n` having sum `n` void printCombinations(int i, int n, vector<int> &out) { // if the sum becomes `n`, print the combination if (n == 0) { printCombination(out); } // start from the previous element in the combination till `n` for (int j = i; j <= n; j++) { // include current element from the combination out.push_back(j); // recur with a reduced sum printCombinations(j, n - j, out); // backtrack: remove the current element from the combination out.pop_back(); } } int main() { int n = 5; vector<int> out; // recur all combinations of numbers from 1 to `n` having sum `n` printCombinations(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
Java
|
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 |
import java.util.Arrays; import java.util.stream.Collectors; class Main { // Recursive function to print all combinations of numbers from `i` to `n` // having sum `n`. The `index` denotes the next free slot in the output array `out` public static void printCombinations(int i, int n, int[] out, int index) { // if the sum becomes `n`, print the combination if (n == 0) { System.out.println(Arrays.stream(out).limit(index) .boxed().collect(Collectors.toList())); } // start from the previous element in the combination till `n` for (int j = i; j <= n; j++) { // place current element at the current index out[index] = j; // recur with a reduced sum printCombinations(j, n - j, out, index + 1); } } public static void main(String[] args) { int n = 5; int[] out = new int[n]; // print all combinations of numbers from 1 to `n` having sum `n` printCombinations(1, n, out, 0); } } |
Output:
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]
Python
|
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 |
# Recursive function to print all combinations of numbers from `i` to `n` # having sum `n`. The `index` denotes the next free slot in the output list `out` def printCombinations(i, n, out, index): # if the sum becomes `n`, print the combination if n == 0: print(out[:index]) # start from the previous element in the combination till `n` for j in range(i, n + 1): # place current element at the current index out[index] = j # recur with a reduced sum printCombinations(j, n - j, out, index + 1) if __name__ == '__main__': n = 5 out = [None] * n # print all combinations of numbers from 1 to `n` having sum `n` printCombinations(1, n, out, 0) |
Output:
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]
The time complexity of the above solution is exponential and requires additional space for the recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)