- Dynamic Programming, Mathematical, Memoization, Natural Numbers, Recursion

Number of M-length sorted arrays that can be formed using first N natural numbers

Number of M-length sorted arrays that can be formed using first N natural numbersGiven two numbers N and M, the task is to find the number of sorted arrays that can be formed of size M using first N natural numbers, if each number can be taken any number of times.Examples:Input: N = 4, M = 2Output: 10Explanation: All such possible arrays are {1, 1}, {1, 2}, {1, 2}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.Input: N = 2, M = 4Output: 5Explanation: All such possible arrays are {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 2}, {1, 2, 2, 2}, {2, 2, 2, 2}.Naive Approach: There are two choices for each number that it can be taken or can be left. Also, a number can be taken multiple times.Elements that are taken multiple times should be consecutive in the array as the array should be sorted.If an element is left and has moved to another element then that element can not be taken again.Recursive Approach: The left branch is indicating that the element is taken and the right branch indicating that the element is left and the pointer moved to the next element.Below is the implementation of the above approach: C++#include using namespace std;  int countSortedArrays(int start, int m,                      int size, int n){            if (size == m)        return 1;      if (start > n)        return 0;      int notTaken = 0, taken = 0;                  taken = countSortedArrays(start, m,                              size + 1, n);          notTaken = countSortedArrays(start + 1,                                 m, size, n);              return taken + notTaken;}  int main(){        int n = 2, m = 3;          cout