# Print all combinations of points from given set of input that can compose a given number. (Recursive & Dynamic approach)

Problem: Print all combinations of points from given a set of input that can compose a given number. (Recursive and Dynamic approach).
Similar Problem: http://www.geeksforgeeks.org/print-all-combinations-of-points-that-can-compose-a-given-number/

Input   : 1 & {1,2,3}
Output: 1

Input   : 2 & {1,2,3}
Output: 2
Explanation: (1 + 1), 2. There are two ways to form number.

Input   : 3 & {1,2,3}
Output: 4
Explanation: (1 + 1 + 1), (1 + 2), (2 + 1), 3

Input   : 4 & {1,2,3}
Output: 7
Explanation:
There are 7 ways to compose value 4 by summation. Set: 1 1 1 1,  1 1 2,  1 2 1, 1 3, 2 1 1, 2 2, 3 1

Solution:
i) Approach 1 (Recursive)

• Create a method which takes a number to be formed and the input set of element
• For each element in the input set, check if number > element from input set
• If yes, make a recursive call by deducting that element from number
• If equal, it means only 1 way left hence (sum += 1)
• If no, skip the entry

ii) Approach 2 (Dynamic)

• Same as above approach but we need to keep the result value at each stage. This will save us many paths that are already been calculated
• For example: Input set {1, 2, 3} and value 4, look in the below image. The node with value 2 has been traversed two times if we go with recursive method. If we can store that value somewhere and use that value when we reach the same node in another path. Code:

Git Url: NumberCombination.java

This interview question was asked in Apple telephonic round.