subset-sum - 子集总和的澄清

Question

这是我的一类编程项目，我不是在寻找答案，而是在寻找对问题的更多解释。我真的不明白在问什么。。

这是另一个输入/输出：输入：1 2 3 3 4 5 输出：1 2 3 3

我不明白我们是如何得到这个输出的，有人可以更简单地向我解释一下吗？谢谢

Answer 1

如果输入为1 2 3 3 4 5，则子序列为：

1
1 2
1 2 3
1 2 3 3
1 2 3 3 4
1 2 3 3 4 5
2
2 3
2 3 3
...

在所有子序列中，1 2 3 3是|(1 + 2 + 3 + 3) - (4 + 5)| = 0最小的。

如果我们取子序列2 3 3，我们有|(2 + 3 + 3) - (1 + 4 + 5)| = |8 - 10| = 2哪个更大。

但是，我也对“子序列”的含义感到困惑。我认为，的子序列1 2 3 4 5应该是：

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
2
2 3
2 3 4
2 3 4 5
3
3 4
3 4 5
4
4 5
5

但是根据主题，最佳子序列1 2 4不在我的列表中。它实际上是 set 的一个子集S。所以要小心，有很多组合。