Print all n | n -- > value of input out -- > output array index -- > index of next digit to be filled in output array evenSum , oddSum -- > sum of even and odd digits so far ; Base case ; If number becomes n - digit ; if absolute difference between sum of even and odd digits is 1 , print the number ; If current index is odd , then add it to odd sum and recurse ; else else add to even sum and recurse ; This is mainly a wrapper over findNDigitNumsUtil . It explicitly handles leading digit and calls findNDigitNumsUtil ( ) for remaining indexes . ; output array to store n - digit numbers ; Initialize number index considered so far ; Initialize even and odd sums ; Explicitly handle first digit and call recursive function findNDigitNumsUtil for remaining indexes . Note that the first digit is considered to be present in even position . ; Driver program
< ? php function findNDigitNumsUtil ( $ n , $ out , $ index , $ evenSum , $ oddSum ) { if ( $ index > $ n ) return ; if ( $ index == $ n ) { if ( abs ( $ evenSum - $ oddSum ) == 1 ) { echo implode ( " " , $ out ) . " " } return ; } if ( $ index & 1 ) { for ( $ i = 0 ; $ i <= 9 ; $ i ++ ) { $ out [ $ index ] = $ i + '0' ; findNDigitNumsUtil ( $ n , $ out , $ index + 1 , $ evenSum , $ oddSum + $ i ) ; } } { for ( $ i = 0 ; $ i <= 9 ; $ i ++ ) { $ out [ $ index ] = $ i + '0' ; findNDigitNumsUtil ( $ n , $ out , $ index + 1 , $ evenSum + $ i , $ oddSum ) ; } } } function findNDigitNums ( $ n ) { $ out = array_fill ( 0 , $ n + 1 , " " ) ; $ index = 0 ; $ evenSum = 0 ; $ oddSum = 0 ; for ( $ i = 1 ; $ i <= 9 ; $ i ++ ) { $ out [ $ index ] = $ i + '0' ; findNDigitNumsUtil ( $ n , $ out , $ index + 1 , $ evenSum + $ i , $ oddSum ) ; } } $ n = 3 ; findNDigitNums ( $ n ) ; ? >