Number of permutation with K inversions | Limit on N and K ; 2D array memo for stopping solving same problem again ; Method recursively calculates permutation with K inversion ; base cases ; If already solved then return result directly ; Calling recursively all subproblem of permutation size N - 1 ; Call recursively only if total inversion to be made are less than size ; Store result into memo ; Driver code
let M = 100 ; let memo = new Array ( M ) ; for ( let i = 0 ; i < M ; i ++ ) { memo [ i ] = new Array ( M ) ; for ( let j = 0 ; j < M ; j ++ ) { memo [ i ] [ j ] = 0 ; } } function numberOfPermWithKInversion ( N , K ) { if ( N == 0 ) return 0 ; if ( K == 0 ) return 1 ; if ( memo [ N ] [ K ] != 0 ) return memo [ N ] [ K ] ; let sum = 0 ; for ( let i = 0 ; i <= K ; i ++ ) { if ( i <= N - 1 ) sum += numberOfPermWithKInversion ( N - 1 , K - i ) ; } memo [ N ] [ K ] = sum ; return sum ; } let N = 4 ; let K = 2 ; document . write ( numberOfPermWithKInversion ( N , K ) ) ;