寻找硬币组合以产生给定零钱的不正确递归方法

Question

我最近在做一个项目欧拉问题（即#31），它基本上是找出使用集合 {1,2,5,10,20,50,100,200} 的元素可以将总和为 200 的方法有多少。

我使用的想法是：求和 N 的方法数等于

（对 Nk 求和的方法数）*（对 k 求和的方法数），对 k 的所有可能值求和。

我意识到这种方法是错误的，即由于它创建了几个重复的计数。我试图调整公式以避免重复，但无济于事。我正在寻求堆栈溢出者的智慧：

1. 我的递归方法是否与要解决的正确子问题有关
2. 如果存在，消除重复的有效方法是什么？
3. 我们应该如何处理递归问题，以便我们关注正确的子问题？我们选择了正确（或不正确）的子问题的一些指标是什么？

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]
        }
    }
}