CODEWITHSUNDEEP
javarecursion
user11452926
user11452926

Reputation: 641

list combinations

How to list combinations in java with methods that stack upon each other.

Upvotes: 0

Views: 46

Answers (1)

Andreas
Andreas

Reputation: 159185

To print the combinations, you need to print when amount == 0.

To do that, you need to accumulate what has been done to get to that value, i.e. which coins has been applied to the amount value.

One way would be to build a string, appending a space and the coin value as part of the recursive call. The resultant string will start with a space, so it has to be skipped when printing.

public static int combo(int amount, int currentCoin, String combo) {
//                                          Added: ^^^^^^^^^^^^^^
    if (amount == 0) {
        System.out.println(combo.substring(1)); // <<<<< Added
        return 1;
    }
    if (amount < 0) {
        return 0;
    }

    int nCombos = 0;
    for (int coin = currentCoin; coin < coins.length; coin++) {
        nCombos += combo(amount - coins[coin], coin, combo + " " + coins[coin]);
        //                                  Added: ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    }

    return nCombos;
}

Test

System.out.println("combo = " + combo(20, 0, ""));
//                                  Added: ^^^^

Output

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 2 5
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 5
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 5 5
1 1 1 1 1 1 1 1 1 2 2 2 5
1 1 1 1 1 1 1 1 2 2 2 2 2 2
1 1 1 1 1 1 1 1 2 5 5
1 1 1 1 1 1 1 2 2 2 2 5
1 1 1 1 1 1 2 2 2 2 2 2 2
1 1 1 1 1 1 2 2 5 5
1 1 1 1 1 2 2 2 2 2 5
1 1 1 1 1 5 5 5
1 1 1 1 2 2 2 2 2 2 2 2
1 1 1 1 2 2 2 5 5
1 1 1 2 2 2 2 2 2 5
1 1 1 2 5 5 5
1 1 2 2 2 2 2 2 2 2 2
1 1 2 2 2 2 5 5
1 2 2 2 2 2 2 2 5
1 2 2 5 5 5
2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 5 5
5 5 5 5
combo = 29

Upvotes: 1

Related Questions