Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k<=n).

eg array is 1 4 6 2 5 & k=3
Output: 3
Sequences: 1 4 6, 1 4 5, 1 2 5


Question is a variant of longest increasing sub sequence problem(LIS Problem) or longest consecutive elements

See http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Data Structure: Array
Algorithm:LIS


Working Code:By Manu

import java.io.*

class LISOfLengthK
{

private static void lisOfLengthK(Integer [] inputArray, int k) {
int n = inputArray.length, temp, count;
Integer [] best = new Integer[n];
Integer [] last = new Integer[n];
Integer [] outputArray = new Integer[k];
for(int i=0;i inputArray[i]) {
best[j] = best[i]+1;
last[j] = i;
if(best[j] == k) {
temp = j;
count =0;
outputArray[count++] = inputArray[temp];
while(last[temp] != -1) {
outputArray[count++] = inputArray[last[temp]];
temp = last[temp];
}
for(int index=k-1;index>=0;index--)
System.out.print(outputArray[index] + " ");
System.out.println();
}
}
}
}
}

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Integer [] inputArray = new Integer[n];
for(int i=0;i inputArray[i] = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
lisOfGivenLength(inputArray, k);
}

}


Time Complexity O(N^2)
Space Complexity O(1)
https://ideone.com/Jbtw0