Coin Change - Permutations - 1

medium

1. You are given a number n, representing the count of coins.
2. You are given n numbers, representing the denominations of n coins.
3. You are given a number "amt".
4. You are required to calculate and print the permutations of the n coins (non-duplicate) using which the amount "amt" can be paid.

Note -&gt; Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

Input Format

A number n n1 n2 .. n number of elements A number amt

Output Format

Check the sample output and question video

Constraints

1 &lt;= n &lt;= 30
0 &lt;= n1, n2, .. n elements &lt;= 20
0 &lt;= amt &lt;= 50

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

2-3-7-.
2-7-3-.
3-2-7-.
3-7-2-.
5-7-.
7-2-3-.
7-3-2-.
7-5-.

Coin Change - Combinations - 2

Coin Change - Permutations - 2