algorithm - 加起来为总和的唯一数字组合

Question

我最近在一次采访中被问到这个问题，完全被难住了。我知道以前有人在这里问过这样的问题，但没有一个能解决抛给这个问题的小问题。

给定一个数字，找出所有可能的方法，你可以只使用数字 1、2、3 将它加起来。所以对于 3 的输入，输出将是 4，因为组合将是 1,1,1 和 1,2 以及 2,1 和 3。我知道硬币找零算法，但它没有给我那个排列1,2 和 2,1。所以我只是最终实现了硬币找零算法并且无法获得排列部分。有人有什么想法吗？

Answer 1

这是一个递归问题:

以5的可能选项为例

X X X X X
1 X X X X
2   X X X
3     X X

所以f(5)=f(4) + f(3) + f(2)

所以通用的解决方案是

f(1)=1
f(2)=2
f(3)=4
f(N)= f(N-1) + f(N-2) + f(N-3) for N > 3