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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
package interviewque; import java.util.ArrayList; import java.util.HashMap; public class NumberCombination { public static int totalCombinationCountRecursive(int[] pointSet, int number) { int sum = 0; for (int i = 0; i < pointSet.length; i++) { if (number > pointSet[i]) { sum += totalCombinationCountRecursive(pointSet, number - pointSet[i]); } else if (number == pointSet[i]) { sum += 1; } } return sum; } public static int totalCombinationCountDynamic(int[] pointSet, int number, HashMap<Integer, Integer> resultMap) { int sum = 0; for (int i = 0; i < pointSet.length; i++) { if (number > pointSet[i]) { if (resultMap.containsKey(number - pointSet[i])) { sum += resultMap.get(number - pointSet[i]); } else { sum += totalCombinationCountDynamic(pointSet, number - pointSet[i], resultMap); } } else if (number == pointSet[i]) { sum += 1; } } resultMap.put(number, sum); return sum; } public static void printCombinationCount(int[] pointSet, int number, ArrayList<Integer> inputArray) { for (int i = 0; i < pointSet.length; i++) { if (number > pointSet[i]) { ArrayList<Integer> newInputArr = new ArrayList<>(inputArray); newInputArr.add(pointSet[i]); printCombinationCount(pointSet, number - pointSet[i], newInputArr); } else if (number == pointSet[i]) { for (Integer integer : inputArray) { System.out.print(integer + " "); } System.out.println(pointSet[i]); } } } public static void main(String[] args) { int[] pointSet = { 1, 2, 3 }; int number = 5; /* * For input 5 * Total combination count is : 13 * Combinations are as below: * 1 1 1 1 1 * 1 1 1 2 * 1 1 2 1 * 1 1 3 * 1 2 1 1 * 1 2 2 * 1 3 1 * 2 1 1 1 * 2 1 2 * 2 2 1 * 2 3 * 3 1 1 * 3 2 */ long startTime = System.nanoTime(); System.out.println("Recursive Total combination count : " + totalCombinationCountRecursive(pointSet, number)); long endTime = System.nanoTime(); System.out.println("Recursive time : " + (endTime - startTime)); HashMap<Integer, Integer> resultMap = new HashMap<Integer, Integer>(); startTime = System.nanoTime(); System.out.println( "Dynamic Total combination count : " + totalCombinationCountDynamic(pointSet, number, resultMap)); endTime = System.nanoTime(); System.out.println("Dynamic time : " + (endTime - startTime)); System.out.println("Total possible combinations are as below:"); ArrayList<Integer> inputArray = new ArrayList<Integer>(); printCombinationCount(pointSet, number, inputArray); } } |
Git Url: NumberCombination.java
This interview question was asked in Apple telephonic round.