CODEWITHSUNDEEP
javaalgorithmcoin-change
Ishan Bhatt
Ishan Bhatt

Reputation: 10239

Change Making algorithm

A typical Change Making problem but a bit twisted. Given a large amount and the denominations given, I need to come up with total number of ways in which the amount can be made using RECURSION. The signature of the function is as follows

int makeChange(int Amount, int[] Denominations)

Amount-Total Amount

Denominations- The available denominatins.

It returns total number of ways.. make sure this has to be done Using Recursion..

Upvotes: 1

Views: 567

Answers (1)

amit
amit

Reputation: 178461

The key idea is to understand at each point you have two choices:

  1. Use the current coin you are looking at, and recurse when decreasing it from amount.
  2. Don't use it, and make it unavailable for later selection.

The function should return the summation of (1) and (2).

Pseudo-code:

makeChange(amount,Denominations):
   //stop clauses:
   if (amount == 0) return 1
   if (amount < 0) return 0
   i <- first index of Denominations where Denominations[i] is not zero
   if there is no such i (all are zero):
        return 0
   num1 = makeChange(amount-Denominations[i],Denominations) //recursive call, using Denominations[i]
   temp <- Denominations[i]
   Denominations[i] = 0
   num2 = makeChange(amount,Denominations) //recursive call, not using Denominations[i] - and will never do again
   Denominations[i] = temp //setting environment back to original
   return num1+num2

java code:

public static int makeChange(int amount, int[] d) { 
    if (amount < 0) return 0;
    if (amount == 0) return 1;
    int i = 0;
    for (i = 0; i < d.length; i++) { 
        if (d[i] != 0) break;
    }
    if (i == d.length) return 0;
    int num1 = makeChange(amount-d[i],d);
    int temp = d[i];
    d[i] = 0;
    int num2 = makeChange(amount,d);
    d[i] = temp;
    return num1 + num2;
}

Upvotes: 4

Related Questions