Function to check if any combination of numbers in a vector will add up to an int?

Question

To start with, I'm looking for something simple and easy to understand rather than the most efficient.

I am trying to create a function that will take in a vector, and an int. The function should return true if any numbers in the vector can add up to the int.

The vector will start with the numbers 1,2,3,4,5,6,7,8,9,10 in it, and throughout the program numbers will be removed. There will be no duplicates of numbers.

The int can be any number from 2 through 12.

Some examples:

• vector = { 2,3,4,5 } int = 7; function returns true because 3 + 4 = 7.
• vector = { 1,5,8 } int = 7; function returns false because none of these numbers can add to 7.
• vector = { 3,6 } int = 3; function returns true because 3 = 3.
• vector = { 5 } int = 2; function returns false because five cannot add to two.

This is the very last function I need to finish a game I am working on. I feel like I'm missing an easy solution, but I'm not sure. Can anyone show me how to do this, or point me in the right direction of how to solve this problem? Thank you in advance.

Answer 1

Given the additional information in the comments, the following function should do (I'm assuming the same number cannot be used twice in the sum):

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;
}

Answer 2

Isn't this a case of the knapsack problem?

See also: subset sum