Given an array arr[] of N elements and a positive integer K such that K ≤ N. The task is to find the number of subsequences of maximum length K i.e. subsequences of length 0, 1, 2, …, K – 1, K that have all distinct elements.
Examples:
Input: arr[] = {2, 2, 3, 3, 5}, K = 2
Output: 14
All the valid subsequences are {}, {2}, {2}, {3}, {3}, {5},
{2, 3}, {2, 3}, {2, 3}, {2, 3}, {2, 5}, {2, 5}, {3, 5} and {3, 5}.Input: arr[] = {1, 2, 3, 4, 4}, K = 4
Output: 24
Approach:
- Sort the array a[] if it is not already sorted and in a vector arr[] store the frequencies of each element of the original array. For example, if a[] = {2, 2, 3, 3, 5} then arr[] = {2, 2, 1} because 2 is present twice, 3 is present twice and 5 only once.
- Say m is the length of the vector arr[]. So m will be the number of distinct elements. There can be subsequences of maximum length m without repetition. If m < k then there is no subsequence of length k. So, declare n = minimum(m, k).
- Now apply dynamic programming. Create a 2-d array dp[n + 1][m + 1] such that dp[i][j] will store the number of subsequences of length i whose first element begins after j-th element from arr[]. For example, dp[1][1] = 3 because it means number
of subsequences of length 1 whose first element starts after 1-st element of arr[] which are {3}, {3}, {5}.- Initialize first row of dp[][] to 1.
- Run two loops top to bottom and right to left inside of the former loop.
- If j > m – i that means there cannot be any such sequences due to lack of elements. So dp[i][j] = 0.
- Else, dp[i][j] = dp[i][j + 1] + arr[j] * dp[i – 1][j + 1] as the number will be number of already existing subsequences of length i plus the number of subsequences of length i – 1 multiplied by arr[j] due to repetition.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Returns number of subsequences // of maximum length k and // contains no repeated element int countSubSeq( int a[], int n, int k) { // Sort the array a[] sort(a, a + n); vector< int > arr; // Store the frequencies of all the // distinct element in the vector arr for ( int i = 0; i < n;) { int count = 1, x = a[i]; i++; while (i < n && a[i] == x) { count++; i++; } arr.push_back(count); } int m = arr.size(); n = min(m, k); // count is the number // of such subsequences int count = 1; // Create a 2-d array dp[n+1][m+1] to // store the intermediate result int dp[n + 1][m + 1]; // Initialize the first row to 1 for ( int i = 0; i <= m; i++) dp[0][i] = 1; // Update the dp[][] array based // on the recurrence relation for ( int i = 1; i <= n; i++) { for ( int j = m; j >= 0; j--) { if (j > m - i) dp[i][j] = 0; else { dp[i][j] = dp[i][j + 1] + arr[j] * dp[i - 1][j + 1]; } } count = count + dp[i][0]; } // Return the number of subsequences return count; } // Driver code int main() { int a[] = { 2, 2, 3, 3, 5 }; int n = sizeof (a) / sizeof ( int ); int k = 3; cout << countSubSeq(a, n, k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Returns number of subsequences // of maximum length k and // contains no repeated element static int countSubSeq( int a[], int n, int k) { // Sort the array a[] Arrays.sort(a); List<Integer> arr = new LinkedList<>(); // Store the frequencies of all the // distinct element in the vector arr for ( int i = 0 ; i < n;) { int count = 1 , x = a[i]; i++; while (i < n && a[i] == x) { count++; i++; } arr.add(count); } int m = arr.size(); n = Math.min(m, k); // count is the number // of such subsequences int count = 1 ; // Create a 2-d array dp[n+1][m+1] to // store the intermediate result int [][]dp = new int [n + 1 ][m + 1 ]; // Initialize the first row to 1 for ( int i = 0 ; i <= m; i++) dp[ 0 ][i] = 1 ; // Update the dp[][] array based // on the recurrence relation for ( int i = 1 ; i <= n; i++) { for ( int j = m; j >= 0 ; j--) { if (j > m - i) dp[i][j] = 0 ; else { dp[i][j] = dp[i][j + 1 ] + arr.get(j) * dp[i - 1 ][j + 1 ]; } } count = count + dp[i][ 0 ]; } // Return the number of subsequences return count; } // Driver code public static void main(String[] args) { int a[] = { 2 , 2 , 3 , 3 , 5 }; int n = a.length; int k = 3 ; System.out.println(countSubSeq(a, n, k)); } } // This code is contributed by PrinciRaj1992 |
Python 3
# Python 3 implementation of the approach # Returns number of subsequences # of maximum length k and # contains no repeated element def countSubSeq(a, n, k): # Sort the array a[] a.sort(reverse = False ) arr = [] # Store the frequencies of all the # distinct element in the vector arr i = 0 while (i < n): count = 1 x = a[i] i + = 1 while (i < n and a[i] = = x): count + = 1 i + = 1 arr.append(count) m = len (arr) n = min (m, k) # count is the number # of such subsequences count = 1 # Create a 2-d array dp[n+1][m+1] to # store the intermediate result dp = [[ 0 for i in range (m + 1 )] for j in range (n + 1 )] # Initialize the first row to 1 for i in range (m + 1 ): dp[ 0 ][i] = 1 # Update the dp[][] array based # on the recurrence relation for i in range ( 1 , n + 1 , 1 ): j = m while (j > = 0 ): if (j > m - i): dp[i][j] = 0 else : dp[i][j] = dp[i][j + 1 ] + \ arr[j] * dp[i - 1 ][j + 1 ] j - = 1 count = count + dp[i][ 0 ] # Return the number of subsequences return count # Driver code if __name__ = = '__main__' : a = [ 2 , 2 , 3 , 3 , 5 ] n = len (a) k = 3 print (countSubSeq(a, n, k)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Returns number of subsequences // of maximum length k and // contains no repeated element static int countSubSeq( int []a, int n, int k) { // Sort the array a[] Array.Sort(a); List< int > arr = new List< int >(); int count, x; // Store the frequencies of all the // distinct element in the vector arr for ( int i = 0; i < n;) { count = 1; x = a[i]; i++; while (i < n && a[i] == x) { count++; i++; } arr.Add(count); } int m = arr.Count; n = Math.Min(m, k); // count is the number // of such subsequences count = 1; // Create a 2-d array dp[n+1][m+1] to // store the intermediate result int [,]dp = new int [n + 1, m + 1]; // Initialize the first row to 1 for ( int i = 0; i <= m; i++) dp[0, i] = 1; // Update the dp[][] array based // on the recurrence relation for ( int i = 1; i <= n; i++) { for ( int j = m; j >= 0; j--) { if (j > m - i) dp[i, j] = 0; else { dp[i, j] = dp[i, j + 1] + arr[j] * dp[i - 1, j + 1]; } } count = count + dp[i, 0]; } // Return the number of subsequences return count; } // Driver code public static void Main(String[] args) { int []a = { 2, 2, 3, 3, 5 }; int n = a.Length; int k = 3; Console.WriteLine(countSubSeq(a, n, k)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Returns number of subsequences // of maximum length k and // contains no repeated element function countSubSeq(a, n, k) { // Sort the array a[] a.sort(); var arr = []; // Store the frequencies of all the // distinct element in the vector arr for ( var i = 0; i < n;) { var count = 1, x = a[i]; i++; while (i < n && a[i] == x) { count++; i++; } arr.push(count); } var m = arr.length; n = Math.min(m, k); // count is the number // of such subsequences var count = 1; // Create a 2-d array dp[n+1][m+1] to // store the intermediate result var dp = Array.from(Array(n+1), ()=>Array(m+1)); // Initialize the first row to 1 for ( var i = 0; i <= m; i++) dp[0][i] = 1; // Update the dp[][] array based // on the recurrence relation for ( var i = 1; i <= n; i++) { for ( var j = m; j >= 0; j--) { if (j > m - i) dp[i][j] = 0; else { dp[i][j] = dp[i][j + 1] + arr[j] * dp[i - 1][j + 1]; } } count = count + dp[i][0]; } // Return the number of subsequences return count; } // Driver code var a = [2, 2, 3, 3, 5]; var n = a.length; var k = 3; document.write( countSubSeq(a, n, k)); </script> |
18
Time Complexity: O(n*log(n)+n*m) where m is the size of the array and n=min(m,k).
Auxiliary Space: O(n*m)
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Returns number of subsequences // of maximum length k and // contains no repeated element int countSubSeq( int a[], int n, int k) { // Sort the array a[] sort(a, a + n); vector< int > arr; // Store the frequencies of all the // distinct element in the vector arr for ( int i = 0; i < n;) { int count = 1, x = a[i]; i++; while (i < n && a[i] == x) { count++; i++; } arr.push_back(count); } // count is the number // of such subsequences int m = arr.size(); n = min(m, k); int count = 1; // to store computations of subproblems vector< int > dp(m + 1, 1); // iterate over subproblems to // get the current solution from previous computations for ( int i = 1; i <= n; i++) { // vector to store current values vector< int > curr(m + 1, 0); for ( int j = m; j >= 0; j--) { if (j > m - i) curr[j] = 0; else { curr[j] = curr[j + 1] + arr[j] * dp[j + 1]; } } // assigning values ot iterate further dp = curr; // update count count = count + dp[0]; } // return final answer return count; } // Driver code int main() { int a[] = { 2, 2, 3, 3, 5 }; int n = sizeof (a) / sizeof ( int ); int k = 3; cout << countSubSeq(a, n, k); return 0; } |
Java
import java.util.Arrays; public class GFG { public static int countSubSeq( int [] a, int k) { // Sort the input array in ascending order Arrays.sort(a); int [] arr = new int [a.length]; // Count the occurrences of each unique element in the sorted array int m = 0 ; for ( int i = 0 ; i < a.length; i++) { int count = 1 ; int x = a[i]; while (i + 1 < a.length && a[i + 1 ] == x) { count++; i++; } arr[m++] = count; } m = Math.min(m, k); int count = 1 ; int [] dp = new int [m + 1 ]; Arrays.fill(dp, 1 ); // Dynamic programming to calculate the count of subsequences for ( int i = 1 ; i <= m; i++) { int [] curr = new int [m + 1 ]; for ( int j = m; j >= 0 ; j--) { if (j > m - i) { curr[j] = 0 ; } else { curr[j] = curr[j + 1 ] + arr[j] * dp[j + 1 ]; } } dp = curr; count += dp[ 0 ]; } return count; } public static void main(String[] args) { int [] a = { 2 , 2 , 3 , 3 , 5 }; // Given input array int k = 3 ; // Maximum number of elements in a subsequence // Calculate and print the total count of subsequences with at most 'k' elements System.out.println(countSubSeq(a, k)); } } |
Python
def countSubSeq(a, k): """ Function to count the number of subsequences of an array 'a' with at most 'k' elements. Args: a (list): The input list containing the elements. k (int): The maximum number of elements in a subsequence. Returns: int: The total count of subsequences with at most 'k' elements. """ a.sort() # Sort the input list in ascending order arr = [] # Count the occurrences of each unique element in the sorted array i = 0 while i < len (a): count = 1 x = a[i] i + = 1 while i < len (a) and a[i] = = x: count + = 1 i + = 1 arr.append(count) m = len (arr) n = min (m, k) count = 1 dp = [ 1 ] * (m + 1 ) # Dynamic programming to calculate the count of subsequences for i in range ( 1 , n + 1 ): curr = [ 0 ] * (m + 1 ) for j in range (m, - 1 , - 1 ): if j > m - i: curr[j] = 0 else : curr[j] = curr[j + 1 ] + arr[j] * dp[j + 1 ] dp = curr count + = dp[ 0 ] return count # Driver code a = [ 2 , 2 , 3 , 3 , 5 ] # Given input list k = 3 # Maximum number of elements in a subsequence # Calculate and print the total count of subsequences with at most 'k' elements print (countSubSeq(a, k)) #user_dtewbxkn77n |
C#
using System; public class GFG { public static int CountSubSeq( int [] a, int k) { // Sort the input array in ascending order Array.Sort(a); int [] arr = new int [a.Length]; // Count the occurrences of each unique element in // the sorted array int m = 0; for ( int i = 0; i < a.Length; i++) { int count = 1; int x = a[i]; while (i + 1 < a.Length && a[i + 1] == x) { count++; i++; } arr[m++] = count; } m = Math.Min(m, k); int totalCount = 1; // Renamed 'count' to 'totalCount' int [] dp = new int [m + 1]; Array.Fill(dp, 1); // Dynamic programming to calculate the count of // subsequences for ( int i = 1; i <= m; i++) { int [] curr = new int [m + 1]; for ( int j = m; j >= 0; j--) { if (j > m - i) { curr[j] = 0; } else { curr[j] = curr[j + 1] + arr[j] * dp[j + 1]; } } dp = curr; totalCount += dp[0]; // Renamed 'count' to 'totalCount' } return totalCount; // Renamed 'count' to // 'totalCount' } public static void Main() { int [] a = { 2, 2, 3, 3, 5 }; // Given input array int k = 3; // Maximum number of elements in a // subsequence // Calculate and print the total count of // subsequences with at most 'k' elements Console.WriteLine(CountSubSeq(a, k)); } } |
Javascript
// Returns number of subsequences // of maximum length k and // contains no repeated element function countSubSeq(a, n, k) { // Sort the array a[] a.sort((x, y) => x - y); const arr = []; // Store the frequencies of all the // distinct element in the array arr let i = 0; while (i < n) { let count = 1; const x = a[i]; i++; while (i < n && a[i] === x) { count++; i++; } arr.push(count); } // count is the number // of such subsequences let m = arr.length; n = Math.min(m, k); let count = 1; // to store computations of subproblems const dp = new Array(m + 1).fill(1); // iterate over subproblems to // get the current solution from previous computations for (let i = 1; i <= n; i++) { // array to store current values const curr = new Array(m + 1).fill(0); for (let j = m; j >= 0; j--) { if (j > m - i) curr[j] = 0; else { curr[j] = curr[j + 1] + arr[j] * dp[j + 1]; } } // assigning values to iterate further dp.splice(0, dp.length, ...curr); // update count count = count + dp[0]; } // return final answer return count; } // Driver code const a = [2, 2, 3, 3, 5]; const n = a.length; const k = 3; console.log(countSubSeq(a, n, k)); |
18
Time Complexity: O(n*log(n)+n*m) where m is the size of the array and n=min(m,k).
Auxiliary Space: O(m)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!