algorithm - 寻找硬币组合以产生给定变化的不正确的递归方法

Question

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

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

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

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

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

Answer 1

在尝试避免重复排列时，在大多数情况下可行的直接策略是仅创建上升或下降序列。

在您的示例中，如果您选择一个值然后对整个集合进行递归，您将得到重复的序列，例如 50,50,100 和 50,100,50 和 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 或 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]
        }
    }
}