Dynamic Programming Approach
Let $n$ = total no. of elements in the set where the elements are in ascending order.
$c(i,j)$ denote the possible no. of numbers of $j$ digits such that the $j^{th}$ digit (from right) is the $i^{th}$ element of the set.
The recurrence relation is as follows-
$c(i, j) = 1, \ j=1$
$c(i, j) = \sum_{k = i}^{n} c(k, j-1) \ \forall \ j>1$
Example
Given, set is $\left \{ 1, 2, 3 \right \}$.
Here, $n = 3$.
Therefore, $c(2,3) = \sum_{k = 2}^{3} c(k, 2) = c(2,2) + c(3,2) = 3$
The resultant table will be as follows-
|
1 digit |
2 digit |
3 digit |
4 digit |
$1^{st}$ element (1) |
1 |
3 |
6 |
10 |
$2^{nd}$ element (2) |
1 |
2 |
3 |
4 |
$3^{rd}$ element (3) |
1 |
1 |
1 |
1 |
NOTE: Cells are filled column wise.
Finally, the given question is asking about finding all such the different possible 4 digit no. that can be formed. This can be obtained by adding the values in the last column, i.e. $c(1,4) + c(2,4) + c(3,4) = 15$
Therefore, required solution is 15.