# Count number of increasing subsequences of size k

Given an array arr[] containing n integers. The problem is to count number of increasing subsequences in the array of size k.

Examples:

```Input : arr[] = {2, 6, 4, 5, 7},
k = 3
Output : 5
The subsequences of size '3' are:
{2, 6, 7}, {2, 4, 5}, {2, 4, 7},
{2, 5, 7} and {4, 5, 7}.

Input : arr[] = {12, 8, 11, 13, 10, 15, 14, 16, 20},
k = 4
Output : 39
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: The idea is to use Dynamic Programming by define 2D matrix, say dp[][]. dp[i][j] stores the count of increasing subsequences of size i ending with element arr[j]. So dp[i][j] can be defined as:

dp[i][j] = 1, where i = 1 and 1 <= j <= n
dp[i][j] = sum(dp[i-1][j]), where 1 < i <= k, i <= j <= n and arr[m] < arr[j] for (i-1) <= m < j.

Below is the implementation of above approach:

## C++

 `// C++ implementation to count number of ` `// increasing subsequences of size k ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// function to count number of increasing ` `// subsequences of size k ` `int` `numOfIncSubseqOfSizeK(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``int` `dp[k][n], sum = 0; ` `    ``memset``(dp, 0, ``sizeof``(dp)); ` ` `  `    ``// count of increasing subsequences of size 1 ` `    ``// ending at each arr[i] ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``dp[i] = 1; ` ` `  `    ``// building up the matrix dp[][] ` `    ``// Here 'l' signifies the size of ` `    ``// increassing subsequnce of size (l+1). ` `    ``for` `(``int` `l = 1; l < k; l++) { ` ` `  `        ``// for each increasing subsequence of size 'l' ` `        ``// ending with element arr[i] ` `        ``for` `(``int` `i = l; i < n; i++) { ` ` `  `            ``// count of increasing subsequnces of size 'l' ` `            ``// ending with element arr[i] ` `            ``dp[l][i] = 0; ` `            ``for` `(``int` `j = l - 1; j < i; j++) { ` `                ``if` `(arr[j] < arr[i]) ` `                    ``dp[l][i] += dp[l - 1][j]; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// sum up the count of increasing subsequences of ` `    ``// size 'k' ending at each element arr[i] ` `    ``for` `(``int` `i = k - 1; i < n; i++) ` `        ``sum += dp[k - 1][i]; ` ` `  `    ``// required number of increasing ` `    ``// subsequences of size k ` `    ``return` `sum; ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = { 12, 8, 11, 13, 10, 15, 14, 16, 20 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``int` `k = 4; ` ` `  `    ``cout << ``"Number of Increasing Subsequences of size "` `         ``<< k << ``" = "` `<< numOfIncSubseqOfSizeK(arr, n, k); ` ` `  `    ``return` `0; ` `} `

## Java

 `//Java implementation to count number of ` `// increasing subsequences of size k ` ` `  `class` `GFG { ` ` `  `// function to count number of increasing ` `// subsequences of size k ` `    ``static` `int` `numOfIncSubseqOfSizeK(``int` `arr[], ``int` `n, ``int` `k) { ` `        ``int` `dp[][] = ``new` `int``[k][n], sum = ``0``; ` ` `  `        ``// count of increasing subsequences of size 1 ` `        ``// ending at each arr[i] ` `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``dp[``0``][i] = ``1``; ` `        ``} ` ` `  `        ``// building up the matrix dp[][] ` `        ``// Here 'l' signifies the size of ` `        ``// increassing subsequnce of size (l+1). ` `        ``for` `(``int` `l = ``1``; l < k; l++) { ` ` `  `            ``// for each increasing subsequence of size 'l' ` `            ``// ending with element arr[i] ` `            ``for` `(``int` `i = l; i < n; i++) { ` ` `  `                ``// count of increasing subsequnces of size 'l' ` `                ``// ending with element arr[i] ` `                ``dp[l][i] = ``0``; ` `                ``for` `(``int` `j = l - ``1``; j < i; j++) { ` `                    ``if` `(arr[j] < arr[i]) { ` `                        ``dp[l][i] += dp[l - ``1``][j]; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// sum up the count of increasing subsequences of ` `        ``// size 'k' ending at each element arr[i] ` `        ``for` `(``int` `i = k - ``1``; i < n; i++) { ` `            ``sum += dp[k - ``1``][i]; ` `        ``} ` ` `  `        ``// required number of increasing ` `        ``// subsequences of size k ` `        ``return` `sum; ` `    ``} ` ` `  `// Driver program to test above ` `    ``public` `static` `void` `main(String[] args) { ` `        ``int` `arr[] = {``12``, ``8``, ``11``, ``13``, ``10``, ``15``, ``14``, ``16``, ``20``}; ` `        ``int` `n = arr.length; ` `        ``int` `k = ``4``; ` ` `  `        ``System.out.print(``"Number of Increasing Subsequences of size "` `                ``+ k + ``" = "` `+ numOfIncSubseqOfSizeK(arr, n, k)); ` ` `  `    ``} ` `} ` `// This code is contributed by 29AjayKumar `

## Python3

# Python3 implementation to count number
# of increasing subsequences of size k
import math as mt

# function to count number of increasing
# subsequences of size k
def numOfIncSubseqOfSizeK(arr, n, k):

dp = [[0 for i in range(n)]
for i in range(k)]

# count of increasing subsequences
# of size 1 ending at each arr[i]
for i in range(n):
dp[i] = 1

# building up the matrix dp[][]
# Here ‘l’ signifies the size of
# increassing subsequnce of size (l+1).
for l in range(1, k):

# for each increasing subsequence of
# size ‘l’ ending with element arr[i]
for i in range(l, n):

# count of increasing subsequnces of
# size ‘l’ ending with element arr[i]
dp[l][i] = 0
for j in range(l – 1, i):
if (arr[j] < arr[i]): dp[l][i] += dp[l - 1][j] # Sum up the count of increasing subsequences # of size 'k' ending at each element arr[i] Sum = 0 for i in range(k - 1, n): Sum += dp[k - 1][i] # required number of increasing # subsequences of size k return Sum # Driver Code arr = [12, 8, 11, 13, 10, 15, 14, 16, 20 ] n = len(arr) k = 4 print("Number of Increasing Subsequences of size", k, "=", numOfIncSubseqOfSizeK(arr, n, k)) # This code is contributed by # Mohit kumar 29 [tabby title="C#"]

 `// C# implementation to count number of ` `// increasing subsequences of size k ` `  `  `using` `System; ` `                     `  `public` `class` `GFG { ` `  `  `// function to count number of increasing ` `// subsequences of size k ` `    ``static` `int` `numOfIncSubseqOfSizeK(``int` `[]arr, ``int` `n, ``int` `k) { ` `        ``int` `[,]dp = ``new` `int``[k,n]; ``int` `sum = 0; ` `  `  `        ``// count of increasing subsequences of size 1 ` `        ``// ending at each arr[i] ` `        ``for` `(``int` `i = 0; i < n; i++) { ` `            ``dp[0,i] = 1; ` `        ``} ` `  `  `        ``// building up the matrix dp[,] ` `        ``// Here 'l' signifies the size of ` `        ``// increassing subsequnce of size (l+1). ` `        ``for` `(``int` `l = 1; l < k; l++) { ` `  `  `            ``// for each increasing subsequence of size 'l' ` `            ``// ending with element arr[i] ` `            ``for` `(``int` `i = l; i < n; i++) { ` `  `  `                ``// count of increasing subsequnces of size 'l' ` `                ``// ending with element arr[i] ` `                ``dp[l,i] = 0; ` `                ``for` `(``int` `j = l - 1; j < i; j++) { ` `                    ``if` `(arr[j] < arr[i]) { ` `                        ``dp[l,i] += dp[l - 1,j]; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` `  `  `        ``// sum up the count of increasing subsequences of ` `        ``// size 'k' ending at each element arr[i] ` `        ``for` `(``int` `i = k - 1; i < n; i++) { ` `            ``sum += dp[k - 1,i]; ` `        ``} ` `  `  `        ``// required number of increasing ` `        ``// subsequences of size k ` `        ``return` `sum; ` `    ``} ` `  `  `// Driver program to test above ` `    ``public` `static` `void` `Main() { ` `        ``int` `[]arr = {12, 8, 11, 13, 10, 15, 14, 16, 20}; ` `        ``int` `n = arr.Length; ` `        ``int` `k = 4; ` `  `  `        ``Console.Write(``"Number of Increasing Subsequences of size "` `                ``+ k + ``" = "` `+ numOfIncSubseqOfSizeK(arr, n, k)); ` `  `  `    ``} ` `} ` `// This code is contributed by 29AjayKumar `

## PHP

 ` `

Output:

```Number of Increasing Subsequences of size 4 = 39
```

Time Complexity: O(kn2).
Auxiliary Space: O(kn).