algorithm - 给定的数组找到给出总和的元素的所有组合

Question

我在面试中被问到以下问题。虽然我已经使用 n 叉树回答了它，但有人告诉我它“不够好”。所以，我很好奇，它的最佳解决方案是什么。

输入:整数数组:[2, 3, 7] 和总和:10

输出:所有加起来为和的数组元素的组合(例如2+2+2+2+2、2+2+3+3、3+7等)

谢谢，

Answer 1

这个问题可以用dynamic programming来解决.你有二维 dp。假设您在名为 mem 的数组中执行 dp。 mem[i][j] 将存储您可以使用索引 j, j + 1... n 的元素实现 sum i 的方法数(此处 n 是数组的大小)。

你有以下关系 mem[i][j] = mem[i][j+1] + mem[i - a[j]][j+1](当然你需要检查 i 是否不小于 a[j])。现在，您可以找到通过获取 mem[S][j] 的值来实现 sum S 的方法的数量。一旦你有了数组，重建解决方案就不是很难了。我建议您尝试自己做，如果您不明白，请发表评论。