Follow up for LC Coin Change, print coin combination


  • 0
    G

    This question was in a Skype interview of a start up IT/Data company, SDE position.

    Same to Coin Change, but we are also required to print the coin combination.

    Each coin is for unlimited reuse. When multiple answers exist, only need to give one of them.

    I couldn't optimize the space complexity but store all of them during that interview, any new thoughts?

    Sample question: coin={1, 3, 2, 5, 7}; target=9, answer should be: {0, 0, 1, 0, 1}


  • 0
    G
        unordered_map<int, vector<int>> dp;
    

    I'm right now thinking about using such a map, each vector stores the combination of coins, with size of coin.size()+1. The last element in the vector is the total number of coins.

    Assume the sample above, the largest element if coin is 7, so when we already get dp[k], we don't need dp[k-7] or smaller, so the space complexity drops to O(k*k).


  • 0

    Here is one simple solution. I wrote this because the question is related to the article https://leetcode.com/articles/coin-change/. You need to keep the state from which you go to the next optimal state.

    
    public int coinChange(int[] coins, int amount) {
    	        int max = amount + 1;             
    	        int[] dp = new int[amount + 1];  
    	        int[] change = new int[amount + 1]; 
    	        Arrays.fill(dp, max);  
    	        dp[0] = 0;   
    	        for (int i = 1; i <= amount;  i++)   {
    	            for (int j = 0;  j  <  coins.length;  j++)  {
    	                if (coins[j]  <=  i)  {
    	                    if (dp[i]  >  dp[i - coins[j]]  +  1)  {
    	                        change[i]  =  j;
    	                        dp[i] = dp[i  -  coins[j]]  +  1;
    	                    }	                 
    	                }
    	            }
    	        }
    	        int cur  =  amount;
    	        do  {
    	            System.out.println(coins[change[cur]]);
    	            cur  -=  coins[change[cur]];
    	        }
    	        while (cur  >  0);
    	       
    	        return dp[amount] > amount ? -1 : dp[amount];
    	    }

  • 0

    My algorithm returns one combination of coins which provide you the minimum change


  • 0
    G

    @elmirap
    Thank you for such an elegant solution!
    So the array "change" keeps a "path"!


  • 0

    @GoGoDong yes, you need to store the previous optimal state in dp


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.