Find all combinations 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
def findCombinationsUtil ( arr , index , num , reducedNum ) : NEW_LINE INDENT if ( reducedNum < 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( reducedNum == 0 ) : NEW_LINE INDENT for i in range ( index ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( " " ) NEW_LINE return NEW_LINE DEDENT prev = 1 if ( index == 0 ) else arr [ index - 1 ] NEW_LINE for k in range ( prev , num + 1 ) : NEW_LINE INDENT arr [ index ] = k NEW_LINE findCombinationsUtil ( arr , index + 1 , num , reducedNum - k ) NEW_LINE DEDENT DEDENT def findCombinations ( n ) : NEW_LINE INDENT arr = [ 0 ] * n NEW_LINE findCombinationsUtil ( arr , 0 , n , n ) NEW_LINE DEDENT n = 5 ; NEW_LINE findCombinations ( n ) ; NEW_LINE