Count Number of Subsequences

Approach: A simple idea to solve this problem is to find all the subsequences and then check the product of every subsequence. This can be done using recursion. 

 

1. Let countSubsequenceHelper(A, P, PR ,IDX) be our recursive function.
   • ‘IDX’  store the index of array element.
   • ‘PR’  store the product of subsequence and take a variable ‘CNT’ (initialized to 0) to count the number of subsequences.
   • We start from ‘IDX’ = 0 and ‘P’ = -1.
   • For every element at index ‘IDX’ i.e. ‘A[IDX]’, there are two choices-either we include ‘A[IDX]’ in subsequence or not.
     • If ‘A[IDX]’ is included:
       • We call the function recursively for ‘IDX’ = ‘IDX + 1’ and ‘PR' = ‘A[i]’  (if current value of ‘PR’ = -1) or ‘PR’ = ‘PR * A[IDX]’ (if ‘PR' != -1) and add result to ’CNT’.
     • If ‘A[IDX]’ is not included:
       • We call the function recursively for ‘IDX’ = ‘IDX + 1’ and ‘PR’ and add the result to ‘CNT’.

 

Base Case:

1. If ‘IDX’ >= ‘N’ and 0 ≤ ‘PR’ ≤ ‘P’, it means we have traversed the complete array and the product of the subsequence is not more than ‘P’.Therefore we found a subsequence and return 1.
2. If ‘IDX' >= 'N’  return 0.
3. Return ‘CNT’.

In the recursive approach, some subproblems are solved again and again.

Let us see the recursion tree for ‘A’ = [1,2,3] and ‘P’ = 4.

It is clear from the recursion tree that the function for (4, 2, 2) is called two times. So to solve this problem of overlapping subproblems, we will use Dynamic programming.

Approach: The basic idea is to use a 2-D array ‘DP’ with ‘P + 1’ rows and ‘N + 1’ columns where a row represents the different values of ‘P’ and column represents the maximum number of elements taken from the array. 

 

1. Take a 2-D array ‘DP[ P + 1 ][ N + 1 ]’ and initialize its values to 0.
2. We will run two loops ‘i’ from 1 to ‘P + 1’ and j from 1 to ‘N + 1’.
3. ‘DP[ i ][ j ]’ stores the count of subsequences having product not more than ‘i’ by taking ‘j’ number of elements from ‘A’.
4. ‘DP[ i ][ j ]’ = count of subsequences having the product, not more than ‘i’ by taking ‘j - 1’ number of elements + count of subsequences formed using ‘ jth ’ element.
5. Count of subsequences by taking ‘j - 1’ number of elements can be found simply at ‘DP[ i ][ j - 1 ]’. So ‘DP[ i ][ j ]’ = ‘DP[ i ][ j - 1 ]’.
6. Now if ‘A[ j - 1 ]’ <= ‘i’
   • ‘DP[ i ][ j ]’ = ‘DP[ i ][ j ]’ + ‘DP[ i / A[ j-1 ] ] [ j-1 ]’.
   • It means we have taken jth element in subsequence and added the count of subsequences with product less than ‘i’ / ‘A[ j - 1 ]’ i.e. ‘DP[ i / [ A ] [ j -1 ]] [ j-1 ]’ .
   • Add 1 to ‘DP[ i ][ j ]’ for a subsequence of only the ‘jth’ element.
7. Return ‘DP[ P ][ N ]’.

 

Algorithm:

1. Initialize a 2-D array ‘DP’ of ‘P’ + 1 row and ‘N’ + 1 column.
2. Run two loops -  ‘i’ from 1 to ‘P’ and ‘j’ from 1 to ‘N’.
3. Store previous result to ‘DP[i][j]’ = ‘DP[i][j - 1]’.
4. If( ‘A[j - 1]’ <= ‘i’) then ‘DP[i][j]’ equals ‘DP[i][j]’ + ‘DP[ i / A[j - 1] ][ j - 1 ]’ +1.
5. Return ‘DP[P][N]’.