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

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

我使用的想法是这样的：求和到 N 的方法的数量等于

（对 N-k 求和的方式数量）*（对 k 求和的方式数量），对 k 的所有可能值求和。

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

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

当试图避免重复排列时，在大多数情况下有效的简单策略是仅创建上升或下降序列。

在您的示例中，如果您选择一个值然后对整个集合进行递归，您将得到重复的序列，例如50,50,100 and 50,100,50 and 100,50,50。但是，如果您按照下一个值应等于或小于当前选定值的规则进行递归，那么在这三个值中，您将仅获得序列100,50,50.

因此，仅计算唯一组合的算法例如：

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)

或者，您可以在每次递归之前创建集合的副本，并从中删除不希望重复的元素。

上升/下降序列方法也适用于迭代。假设您想要找到三个字母的所有唯一组合。该算法将打印如下结果a,c,e， 但不是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]
        }
    }
}