**PROBLEM LINK:** Is it Sorted or Not, That is the Question

**AUTHOR:** panik

**DIFFICULTY:** Medium

**PREREQUISITES:** Dynamic Programming

**Solution:**

We first find out the no. of distinct no.s and their frequency in the array. Let us denote this Frequency array by F. We do this because we need to find all sorted the sequences of length K. So we can approach this problem by thinking how many occurrences of some particular distinct element will we pick in a particular sequence for each distinct element. After this is decided the no. of ways of obtaining this sequence is the summation of ( factorial(no. of elements you picked of ith distinct element)) for all distinct elements. For eg, you have an array 1 2 2 and K=3, so you have 2 occurrences of 2 and 1 occurrence of 1. so no. of ways of obtaining a valid sequence is 1! * 2!.

After that, we create an array DP[ i ][ j ] where the ith state denotes the index of the distinct no. we are on and j represents the no. elements that have been picked by us. we approach this DP in a top-down fashion and for any particular state, we find its value by taking the summation of all values obtained if xth occurrences of the ith distinct element are picked. Refer to my solution for More clarity as its well commented for your ease.

**Expected solution**: here