Count of subsequences in an array with sum less than or equal to X | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubsequenceUtil ( int ind , int sum , int * A , int N , vector < vector < 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 ] ; } int countSubsequence ( int * A , int N , int X ) { vector < vector < int > > dp ( N , vector < int > ( X + 1 , -1 ) ) ; return countSubsequenceUtil ( 0 , X , A , N , dp ) - 1 ; } int main ( ) { int arr [ ] = { 25 , 13 , 40 } , X = 50 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countSubsequence ( arr , N , X ) ; return 0 ; }