改进子集解决方案

Question

我有一个实践问题，我有一个给定的值和给定的数组数组。我可以使用给定数组中的任何值创建一个等于给定值的和。

原来，我的算法会遍历每个可能的组合的数组。我后来对它进行了优化，以检查当前总和是否大于该值。如果是这样，请停止尝试后面的组合，因为它们都将大于该值。

出于好奇，最好是先计算所有的总和，然后对总和进行排序，然后进行二分搜索以找到等值的总和？我想象一下，在每一笔款项中进行比较将比预算和结果慢得多。

Answer 1

会计算所有的总和，然后搜索一个等于所需值的总和比单纯的强力搜索更高效（及时）吗？

如果我们考虑最糟糕的情况，那么这两个解决方案所需的添加操作的数量是相等的，因为您已经计算了解决方案中的每个和，而蛮力搜索最终会尝试每种组合。

在您的解决方案中进行比较的次数是否小于或等于使用强力比较的次数？是。您绝对不需要首先计算所有的总和，然后对结果进行排序：您可以在进行所有计算时简单地构建排序集。暴力强制最终会做与组合一样多的比较，但建立所有总和的排序集合，然后对匹配值进行二分搜索不应该是指数级的。

但是接下来，你可能已经找到了一个解决方案，而你正在建立你的电源设置，所以我不知道它与简单的蛮力相比有多大的不同。它看起来像一个更昂贵的蛮力，因为如果你愿意这样做，你现在必须处理所有这些总和和其他中间计算。