Count of subsequences in an array with sum less than or equal to X | Utility function to return the count of subsequence in an array with sum less than or equal to X ; Base condition ; Return if the sub - problem is already calculated ; Check if the current element is less than or equal to sum ; Count subsequences excluding the current element ; Count subsequences including the current element ; Exclude current element ; Return the result ; Function to return the count of subsequence in an array with sum less than or equal to X ; Initialize a DP array ; Return the result ; Driver Code
function countSubsequenceUtil ( ind , sum , A , N , dp ) { if ( ind == N ) return 1 ; if ( dp [ ind ] [ sum ] != - 1 ) return dp [ ind ] [ sum ] ; if ( A [ ind ] <= sum ) { dp [ ind ] [ sum ] = countSubsequenceUtil ( ind + 1 , sum , A , N , dp ) + countSubsequenceUtil ( ind + 1 , sum - A [ ind ] , A , N , dp ) ; } else { dp [ ind ] [ sum ] = countSubsequenceUtil ( ind + 1 , sum , A , N , dp ) ; } return dp [ ind ] [ sum ] ; } function countSubsequence ( A , N , X ) { let dp = new Array ( N ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < X + 1 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return countSubsequenceUtil ( 0 , X , A , N , dp ) - 1 ; } let arr = [ 25 , 13 , 40 ] , X = 50 ; let N = arr . length ; document . write ( countSubsequence ( arr , N , X ) ) ;