Last Updated: 24 Feb, 2021

# Making Wands

Moderate

## Problem statement

#### Albus wants to see wands of different powers, so Harry did magic and did the following things.

``````Harry chooses zero or more wands of power ‘A’ and zero or more wands of power ‘B’. He chose exactly ‘K’ wands.

Then Harry adds the power of all ‘K’ wands and made a new wand of power equal to the sum of powers of ‘K’ chosen wands.
``````

#### Harry is getting late for his meeting at the Ministry of Magic. So, he called you for help.

##### Input Format
``````The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains three space-separated integers ‘A’, ‘B’, and ‘K’.
``````
##### Output Format:
``````For each test case, print the powers of all unique wands in sorted order separated by a single space.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 5
1 <= K <= 5000
0 <= A, B  <= 10 ^ 5

Time Limit: 1sec
``````

## Approaches

### 01 Approach

The idea here is to generate all possible combinations of wands. At each step, we have two choices either combine a wand of power ‘A’ or combine a wand power ‘B’. So, we will solve this problem recursively by making two recursive calls at each step, one for power ‘A’ and other for power ‘B’.

Algorithm:

• Declare an array to store all unique wands say, ‘answer’.  Also declare a hash set say, ’hashSet’ to keep track of duplicate wands.
• Call ‘doRecursive’ function to store all unique wands in ‘answer’ array.

Description of ‘doRecursive’ function.

This function is used to generate all possible combinations of wands.

This function will take six parameters.

• A: An integer denoting the power of wand of type ‘A’.
• B: An integer denoting the power of wand of type ‘B’.
• current: An integer denoting the power of the current combination of the wand.
• K: An integer that denotes the number of wands that are left in the current recursive call.
• answer: An array to store all unique wands.
• hashSet: An hash set to keep track of duplicate wands.

doRecursive(A, B, current, K, answer, hashSet):

• If ‘K’ equals 0 then if ‘current’ is not present in the ‘hashSet’ then add ‘current’ to ‘answer’ and ‘hashSet’ and break the recursion as we have used maximum allowed wands.
• Add ‘A’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + A, K - 1, answer, hashSet)’.
• Add ‘B’ to current and recursively the function by decrementing value of ‘K’ i.e. call ‘doRecursive(A, B, current + B, K - 1, answer, hashSet)’.