×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Java
Posted by: Shamir Yona
Added: Jun 19, 2016 5:51 PM
Views: 3
Tags: recursion
Calculate the # of coins that sum to an input sum
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package moreTests;
  7.  
  8. import java.util.Arrays;
  9.  
  10. /**
  11.  *
  12.  * @author shayzukerman
  13.  */
  14. public class CoinChange
  15. {
  16.     public static void coinChange(int amount, int[] coins)
  17.     {
  18.         int[] cnt4coin = new int[coins.length];
  19.         Arrays.fill(cnt4coin, 0);
  20.        
  21.         coinChangeEx(amount, coins, 0, cnt4coin);
  22.     }
  23.    
  24.     public static void coinChangeEx(int left, int[] coins, int coinIdx, int[] cnt4coin)
  25.     {
  26.         if (left <= 0 || coinIdx == coins.length)
  27.             return;
  28.        
  29.         int currCoin = coins[coinIdx];
  30.         int maxNr4Coin = left / currCoin;
  31.         for (int val = 0; val <= maxNr4Coin; val++)
  32.         {
  33.             cnt4coin[coinIdx] = val;
  34.             int tmpLeft = left - val * currCoin;
  35.             if (tmpLeft == 0)
  36.                 printCoins(coins, cnt4coin);
  37.             else if (tmpLeft > 0 && coinIdx < coins.length)
  38.                 coinChangeEx(tmpLeft, coins, coinIdx + 1, cnt4coin);
  39.         }
  40.     }
  41.    
  42.     public static void printCoins(int[] coins, int[] cnt4coin)
  43.     {
  44.         System.out.print("{");
  45.         for (int i = 0; i < cnt4coin.length; i++)
  46.         {
  47.             int cnt = cnt4coin[i];
  48.             for (int j = 0; j < cnt; j++)
  49.                 System.out.format("%d ", coins[i]);
  50.         }
  51.         System.out.println("}");
  52.     }
  53.    
  54.     public static void main(String[] args)
  55.     {
  56.         int[] coins = {1, 2, 3};
  57.         int amount = 5;
  58.        
  59.         coinChange(amount, coins);
  60.     }
  61. }
  62.