In the previous solution for the same permutations problem, we used the formula of permutation coefficient and printed all permutations by taking LEVELS as ITEMS and CHOICES/EDGES as BOXES in the recursion tree.
In this solution, we will find a relation between binomial expansion and the permutation coefficient. Hence, we will try to find permutations by taking LEVELS as BOXES and find out what should be the choices.

Q) Can you see a relation, and find out how all the permutations of r non-identical items (1, 2, 3, .. r) can be generated using the binomial expansion?

• In combinations, for each box, we had only two choices, whether to place an identical item (i) or not.
• But for permutations, since the items are non-identical, instead of having 2 choices, we will have r + 1 choices.
• These choices will be: whether to place 1st item in the current box, or 2nd item in the current box, ... rth item in the current box or do not place any item.

Hence in a recursion tree, LEVELS are equivalent to BOXES, but the CHOICES/EDGES are ITEMS = 1, 2, 3, ... r or no item (0).

Let us quickly define the expectation, faith and finally meet our expectations with the faith.
Expectation: We expect that the recursive function will give us all the permutations of r non-identical items. At each level, we are deciding for the current box cb.

Here, cb is the current box whose decision is to be taken, tb is the total number of boxes, ssf is the number of items placed so far, ts is the total number of identical items, and asf is the answer so far.
Also, there is an items array which will store the box number, in which the item is stored. If items[i] = j, it means ith item is placed in jth box. If the item is not placed yet, then items[i] should be 0.
Faith: We will keep faith on the recursive function that will help us make all the choices for the remaining n-1 boxes.

Meeting Expectation with Faith:

For the current box, we have r + 1 options, whether we should place an item in it or let it remain empty.
But, an item can be placed in the current box only if it has not been placed in any of the previous boxes.
Hence, we will run a loop over all the items [0, r-1] and check whether the current item is placed or not. If it is not placed yet (item[i] == 0), then we will place it in the current box, by updating item[i] = cb, in the node-pre area.
After placing an item, we will recursively call for the remaining boxes by increasing cb by 1, adding the item to the answer so far, and incrementing items placed so far by 1.
Also, after returning from the recursive function of remaining boxes, i.e in the edge-post area, we will update the current box back to empty (item[i] = 0) .

We have explored r choices out of the available r + 1 choices. The only choice remaining to be executed is to not place any item in the current box. Hence, we will simply call for the next box (cb + 1) and add "-" (empty box) to the answer so far .

Base Case
Since we are picking all the boxes level by level, we should stop when decisions for all the boxes have been made. Hence, we should stop when the current box becomes greater than the total boxes (cb > tb).
Now, there is a catch. As discussed in the mathematical formula, we will generate all the permutations of 0 items, 1 items, 2 items, and so on. But we only require those permutations which have ts (total number of non- identical) items in the answer string. Hence, we will print the permutation only if ssf = ts.