Count of subsequences in an array with sum less than or equal to X | Java program to count number 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
class GFG { static int countSubsequenceUtil ( int ind , int sum , int [ ] A , int N , int [ ] [ ] 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 ] ; } static int countSubsequence ( int [ ] A , int N , int X ) { int [ ] [ ] dp = new int [ N ] [ X + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < X + 1 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return countSubsequenceUtil ( 0 , X , A , N , dp ) - 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 25 , 13 , 40 } , X = 50 ; int N = arr . length ; System . out . print ( countSubsequence ( arr , N , X ) ) ; } }