Incorrect Recursive approach to finding combinations of coins to produce given change

Question

I was recently doing a project euler problem (namely #31) which was basically finding out how many ways we can sum to 200 using elements of the set {1,2,5,10,20,50,100,200}.

The idea that I used was this: the number of ways to sum to N is equal to

(the number of ways to sum N-k) * (number of ways to sum k), summed over all possible values of k.

I realized that this approach is WRONG, namely due to the fact that it creates several several duplicate counts. I have tried to adjust the formula to avoid duplicates, but to no avail. I am seeking the wisdom of stack overflowers regarding:

1. whether my recursive approach is concerned with the correct subproblem to solve
2. If there exists one, what would be an effective way to eliminate duplicates
3. how should we approach recursive problems such that we are concerned with the correct subproblem? what are some indicators that we've chosen a correct (or incorrect) subproblem?

Answer 1

When trying to avoid duplicate permutations, a straightforward strategy that works in most cases is to only create rising or falling sequences.

In your example, if you pick a value and then recurse with the whole set, you will get duplicate sequences like 50,50,100 and 50,100,50 and 100,50,50. However, if you recurse with the rule that the next value should be equal to or smaller than the currently selected value, out of those three you will only get the sequence 100,50,50.

So an algorithm that counts only unique combinations would be e.g.:

function uniqueCombinations(set, target, previous) {
    for all values in set not greater than previous {
        if value equals target {
            increment count
        }
        if value is smaller than target {
            uniqueCombinations(set, target - value, value)
        }
    }
}

uniqueCombinations([1,2,5,10,20,50,100,200], 200, 200)

Alternatively, you can create a copy of the set before every recursion, and remove the elements from it that you don't want repeated.

The rising/falling sequence method also works with iterations. Let's say you want to find all unique combinations of three letters. This algorithm will print results like a,c,e, but not a,e,c or e,a,c:

for letter1 is 'a' to 'x' {
    for letter2 is first letter after letter1 to 'y' {
        for letter3 is first letter after letter2 to 'z' {
            print [letter1,letter2,letter3]
        }
    }
}