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
< ? php function findCombinationsUtil ( $ arr , $ index , $ num , $ reducedNum ) { if ( $ reducedNum < 0 ) return ; if ( $ reducedNum == 0 ) { for ( $ i = 0 ; $ i < $ index ; $ i ++ ) echo $ arr [ $ i ] , " ▁ " ; echo " STRNEWLINE " ; return ; } $ prev = ( $ index == 0 ) ? 1 : $ arr [ $ index - 1 ] ; for ( $ k = $ prev ; $ k <= $ num ; $ k ++ ) { $ arr [ $ index ] = $ k ; findCombinationsUtil ( $ arr , $ index + 1 , $ num , $ reducedNum - $ k ) ; } } function findCombinations ( $ n ) { $ arr = array ( ) ; findCombinationsUtil ( $ arr , 0 , $ n , $ n ) ; } $ n = 5 ; findCombinations ( $ n ) ; ? >