algorithm - 显示方程 x1+x2+...+xk = n 的所有正解

Question

下面是显示方程 x1+x2+...+xk = n 的所有正解的程序，其中 k 和 n 是正整数:

func solution(k: Int, n: Int) {
    if k > n || k <= 0 {
        print("No solution")
    } else 
        if k==1 {
            print(n)
        } else {
            for i in 1...(n-k+1) {
                print(i, terminator:"")

                solution(k-1, n: n-i)
                print("")
            }
        }
}
solution(4, n: 4)

此程序在 n = 4 和 k = 1,2,4 时运行良好，但在 k = 3 时显示不正确。有人可以帮助找出错误吗？

Answer 1

问题是对于 n = 4 和情况 k = 1、2、4，每个 i 只有一个解决方案，因此您的 print(i, terminator:"") 可以正常工作。

但是，对于 k = 3 的情况，例如，在 k = 3 处打印 1 之后，因此有不止一个正确的情况:(1 , 2, 1) 或 ( 1, 1, 2)，这意味着在 k = 1 处只有一个命令 print(1, terminator:"") 是不够的。

图像打印例程将像这样:

at k = 3, i = 1, print 1

at k = 2, i = 1, print 1

at k = 1, i = 2, print 2

So, at this time, we have (1, 1, 2), looks good.

However, when we backtrack to k = 2, i = 2, print 2

at k = 1, i = 1, print 1,

So, we only have (2, 1), which is not correct.

解决这个问题的一个简单方法是不要在每个递归步骤都打印，您只需将所有结果存储在一个数组中，并在 k 达到 0 时打印该数组