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

Question

我最近在一次采访中被问到这个问题，完全被难住了。我知道之前有人在这里问过这样的问题，但 none 处理了这个问题上的小问题。

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

Answer 1

回答你关于问题分类的问题对我来说它看起来像动态规划问题。请参阅以下摘自 stanford.edu

的问题

一维DP示例

◮ Problem: given n, find the number of different ways to write
n as the sum of 1, 3, 4
◮ Example: for n = 5, the answer is 6
5 = 1 + 1 + 1 + 1 + 1
= 1 + 1 + 3
= 1 + 3 + 1
= 3 + 1 + 1
= 1 + 4
= 4 + 1

这里是 solution to similar problem

Answer 2

这是一个递归问题：

以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

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

Unique combinations of numbers that add up to a sum

algorithm

combinations

permutation