You are given an integer array of coin values and an integer representing the total amount of money. Return the number of possible ways to change the money into coins.
Input: sum = 3, coins[] = {1,2,3} Output: 3 Explanation: There are 3 solutions: {1,1,1}, {1,2}, {3} Input: sum = 9, coins[] = {2,4,3,5} Output: 5 Explanation: There are 5 solutions: {2,2,2,3}, {3,3,3}, {4,2,3}, {4,5}, {2,2,5} |
Solution:
1. public static int count(int[] coins, int sum) { 2. int[] table = new int[sum + 1]; 3. table[0] = 1; 4. for (int coin: coins) 5. for (int j = coin; j <= sum; j++) 6. table[j] += table[j - coin]; 7. 8. return table[sum]; 9. } 10.
Comments