#define ARR_SIZE 100
#include<stdio.h>
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* The function prints all combinations of numbers 1, 2, ...n
that sum up to n. i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n,int m ,int i)
{
/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= m; k++)
{
arr[i]= k;
printCompositions(n-k,m, i+1);
}
}
}
/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 , 3 , 4 and 5 %d are\n", n);
printCompositions(n,n, 0);
getchar();
return 0;
}
Time Complexity O(n^m) Exponential
Space Complexity O(m)
Run Here http://ideone.com/clone/ETZTv
