c++ - 检查 vector 中数字的任何组合是否会加起来为 int 的函数？

Question

首先，我正在寻找简单易懂的东西，而不是最有效的东西。

我正在尝试创建一个函数，它将接受一个vector 和一个int。如果 vector 中的任何数字加起来等于 int，该函数应返回 true。

vector 将从其中的数字 1,2,3,4,5,6,7,8,9,10 开始，整个程序中的数字将被删除。不会有重复的数字。

int 可以是 2 到 12 之间的任何数字。

一些例子:

• vector = { 2,3,4,5 } int = 7; 函数返回 true 因为 3 + 4 = 7。
• vector = { 1,5,8 } int = 7; 函数返回 false 因为这些数字中没有一个可以加到 7。
• vector = { 3,6 } int = 3; 函数返回 true 因为 3 = 3。
• vector = { 5 } int = 2; 函数返回 false 因为五不能加到二。

这是我完成正在开发的游戏所需的最后一个函数。我觉得我缺少一个简单的解决方案，但我不确定。任何人都可以告诉我如何做到这一点，或者指出如何解决这个问题的正确方向吗？提前谢谢你。

Answer 1

鉴于注释中的附加信息，应该执行以下函数(我假设相同的数字不能在总和中使用两次):

typedef std::vector<int>::iterator iter;
bool contains_sum(iter begin, iter end, int sum)
{
  while (begin != end)
  {
    --end;
    if (*end > sum)
      continue;
    if (contains_sum(begin, end, sum - *end))
      return true;
  }
  return sum == 0;
}