CODEWITHSUNDEEP
javaalgorithmrecursioncoin-change
Spindoctor
Spindoctor

Reputation: 471

Coin Change Recursion All Solutions to Distinct Solutions

I am new to recursion and backtracking. I know I need to be completely comfortable with these concepts before I move on to dynamic programming. I have written a program below that helps me find all the possible combinations for a given amount n and an unlimited number of coins. However, I wish to have my program give me distinct solutions. I am having a hard time figuring out how to do this.

I have found a resource here: Coin Change that uses a top down approach recursively and then modifies it to give distinct combinations using the following formula: count (s, n, total) = count (s, n, total-s[n]) + count(s, n-1, total)

This says that I recurse using the value and then recurse excluding the value and decreasing the coins by 1.

I can't seem to grasp how this works. Also I can for sure say, it would have been quite hard to even think of such a technique on the spot at an interview per say. It seems like some one at some point would have had to spend a considerable amount of time on such a problem to devise such a technique.

Anyhow any help on how I can convert my program to print distinct solutions and how it works will be really appreciated.

public class Recursive {

    static int[] combo = new int[100];
    public static void main(String argv[]) {
        int n = 8;
        int[] amounts = {1, 5, 10};
        ways(n, amounts, combo, 0, 0, 0);
    }

    public static void  ways(int n, int[] amounts, int[] combo, int count, int sum, int index) {
        if(sum == n) {
            printArray(combo, index);
        }

        if(sum > n) {
            return;
        }


        for(int i=0;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, 0, sum, index + 1);
            sum = sum - amounts[i];
        }
    }

    public static void printArray(int[] combo, int index) {
        for(int i=0;i < index; i++) {
            System.out.print(combo[i] + " ");
        }
        System.out.println();
    }
}

The actual amount of non distinct valid combinations for amounts {1, 2, 5} and N = 10 is 128, using a pure recursive exhaustive technique (Code below).

My question is can an exhaustive search be improved with memoization/dynamic programming. If so, how can I modify the algorithm below to incorporate such techniques.

Upvotes: 0

Views: 1240

Answers (2)

Spindoctor
Spindoctor

Reputation: 471

static HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public static void main(String argv[]) {
        int n = 1000;
        System.out.println(getSteps(n, 0,0 ));
    }

    public static int getSteps(int n, int sum, int count) {

        if(n == sum) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        if(memo.containsKey(sum)) {
            return memo.get(sum);
        }
        for(int i=1; i<=3;i++) {
            sum = sum + i;
            count += getSteps(n, sum, 0);
            sum = sum - i;
            memo.put(sum, count);
        }
        return count;
    }

Upvotes: 0

MBo
MBo

Reputation: 80107

Simple modification allow to avoid repeats.

Use sorted amounts array.
Starting value of the loop should exclude previous values from amounts.
I used count argument (seems unused)

 for(int i=count;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, i, sum, index + 1);
            sum = sum - amounts[i];
        }

Upvotes: 2

Related Questions