Count the number of ordered sets not containing consecutive numbers | DP table ; Function to calculate the count of ordered set for a given size ; Base cases ; If subproblem has been soved before ; Store and return answer to this subproblem ; Function returns the count of all ordered sets ; Prestore the factorial value ; Initialise the dp table ; Iterate all ordered set sizes and find the count for each one maximum ordered set size will be smaller than N as all elements are distinct and non consecutive . ; Multiply ny size ! for all the arrangements because sets are ordered . ; Add to total answer ; Driver code
var dp = Array . from ( Array ( 500 ) , ( ) => Array ( 500 ) ) ; function CountSets ( x , pos ) { if ( x <= 0 ) { if ( pos == 0 ) return 1 ; else return 0 ; } if ( pos == 0 ) return 1 ; if ( dp [ x ] [ pos ] != - 1 ) return dp [ x ] [ pos ] ; var answer = CountSets ( x - 1 , pos ) + CountSets ( x - 2 , pos - 1 ) ; return dp [ x ] [ pos ] = answer ; } function CountOrderedSets ( n ) { var factorial = Array ( 10000 ) . fill ( 0 ) ; factorial [ 0 ] = 1 ; for ( var i = 1 ; i < 10000 ; i ++ ) factorial [ i ] = factorial [ i - 1 ] * i ; var answer = 0 ; dp = Array . from ( Array ( 500 ) , ( ) => Array ( 500 ) . fill ( - 1 ) ) ; for ( var i = 1 ; i <= n ; i ++ ) { var sets = CountSets ( n , i ) * factorial [ i ] ; answer = answer + sets ; } return answer ; } var N = 3 ; document . write ( CountOrderedSets ( N ) ) ;