c++ - 子集问题——任何材料？

Question

是的，这是一项家庭作业/实验室作业。我很有趣想出/找到一种算法（我可以理解：P）来使用“回溯”来解决子集和问题。

有人有一些有用的资源吗？我花了最后一个小时左右的时间在谷歌上搜索，并不太想找到我认为我可以实际使用的东西。xD

谢谢！

Answer 1

将数据放入向量中。

然后编写一个具有 3 个参数的例程：向量、索引和总和。使用以下参数调用此例程：向量、0、0。

该例程应执行以下任务：

• 检查我们是否到达了向量的末尾（索引==大小）。如果是这种情况，我们可以立即返回。
• 使用参数调用自身：向量、索引+1、总和+向量[索引]（在这种情况下，我们将索引处的元素添加到总和并继续向量）
• 使用参数调用自身：向量、索引+1、总和（在这种情况下，我们不会将索引处的元素添加到总和中，但仍会继续）

我故意在这个算法中省略了 2 个部分：

• 首先，您应该在某个时候检查总和。如果它是零，那么你找到了一个正确的子集
• 其次，您还应该传递有关您使用了哪些元素的知识，因此如果总和为零，您可以打印出子集。考虑为此使用 STL::set。

或者，您可以使用函数的返回值来确定是否已找到正确的子集。

该算法的复杂度为 O(2^N)，因此对于大集合来说会非常慢。

玩得开心。