fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Solution{
  6. 	public static void main (String[] args) throws java.lang.Exception{
  7.             System.out.println(getChange(new int[]{1,6,9},30));
  8.             System.out.println(getChange(new int[]{1},3));
  9.             System.out.println(getChange(new int[]{4,20,500},450));
  10. 	}
  11.  
  12. 	private static List<Integer> getChange(int[] denominations,int amount){
  13.             Arrays.sort(denominations);
  14.             List<Integer> ans = new ArrayList<>();
  15.             if(amount <= 0 || denominations[0] > amount) return ans;
  16.             int[][] dp = new int[amount + 1][2];
  17.  
  18.             for(int i=0;i<denominations.length;++i){
  19.                 if(denominations[i] > amount) break;
  20.                 dp[denominations[i]][0] = 1;
  21.                 dp[denominations[i]][1] = 0;
  22.                 for(int j=denominations[i] + 1;j<=amount;++j){
  23.                     if(dp[j-denominations[i]][0] > 0 && (dp[j][0] == 0 || dp[j-denominations[i]][0] + 1 < dp[j][0])){
  24.                        dp[j][0] = dp[j-denominations[i]][0] + 1;
  25.                        dp[j][1] = j-denominations[i];
  26.                     }
  27.                 }
  28.             }
  29.  
  30.             if(dp[amount][0] > 0){
  31.                 while(dp[amount][0] != 0){
  32.                     ans.add(amount - dp[amount][1]);
  33.                     amount = dp[amount][1];
  34.                 }
  35.             }
  36.  
  37.  
  38.  
  39.             return ans;
  40. 	}
  41. }
Success #stdin #stdout 0.06s 32468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[9, 9, 6, 6]
[1, 1, 1]
[]
https://ideone.com/2fYg4F
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!