Find all combinations that add upto given number | C ++ program to find out all combinations of positive numbers that add upto given number ; arr - array to store the combination index - next location in array num - given number reducedNum - reduced number ; Base condition ; If combination is found , print it ; Find the previous number stored in arr [ ] It helps in maintaining increasing order ; note loop starts from previous number i . e . at array location index - 1 ; next element of array is k ; call recursively with reduced number ; Function to find out all combinations of positive numbers that add upto given number . It uses findCombinationsUtil ( ) ; array to store the combinations It can contain max n elements ; find all combinations ; Driver code
#include <iostream> NEW_LINE using namespace std ; void findCombinationsUtil ( int arr [ ] , int index , int num , int reducedNum ) { if ( reducedNum < 0 ) return ; if ( reducedNum == 0 ) { for ( int i = 0 ; i < index ; i ++ ) cout << arr [ i ] << " ▁ " ; cout << endl ; return ; } int prev = ( index == 0 ) ? 1 : arr [ index - 1 ] ; for ( int k = prev ; k <= num ; k ++ ) { arr [ index ] = k ; findCombinationsUtil ( arr , index + 1 , num , reducedNum - k ) ; } } void findCombinations ( int n ) { int arr [ n ] ; findCombinationsUtil ( arr , 0 , n , n ) ; } int main ( ) { int n = 5 ; findCombinations ( n ) ; return 0 ; }