C/C++ implementation of a subset sum kind of problem

Question

I think that stackoverflow is rendering me even lazier than usual, but...

The problem is simpler than knapsack (or a type of it, without values and only positive weights). It consists on checking if a number can be a combination of others, and the function shall return true or false.

Ex: 112 and a list with { 17, 100, 101 } should return false, 469 with the same list should return true, 35 should return false, 119 true, etc...

Any ideas? Thanks!

Edit: subset sum problem would be more accurate for this than knapsack.

Answer 1

An observation that will help you is that if your list is {a, b, c...} and the number you want to test is x, then x can be written as a sum of a sublist only if either x or x-a can be written as a sum of the sublist {b, c, ...}. This lets you write a very simple recursive algorithm to solve the problem.

edit: here is some code, taking into account the comments below. Not tested so probably buggy; and not necessarily the fastest. But for a small dataset it will get the job done neatly.

bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end)
{
  // for a 1-element list {a} we just need to test a|x
  if (start == end) return (x % *start == 0); 

  // if x is small enough  we don't need to bother testing x - a
  if (x<a) return is_subset_sum (x, start+1, end);

  // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive.
  return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end));
}

Answer 2

This is a special case of the Subset Sum problem, with sets that only contain one negative number (i.e., express 112 and { 17, 100, 101 } as { -112, 17, 100, 101 }). There's a few algorithms on the Wikipedia page, http://en.wikipedia.org/wiki/Subset_sum_problem.

Answer 3

Note that positive results become denser as the queried number becomes larger. For example, all numbers greater than 100^2 can be generated by { 17, 100, 101 }. So the optimal algorithm may depend upon whether the queried number is much greater than the set's members. You might look into field theory.

At the least, you know the result is always false if the greatest common divisor of the set is not in the query, and that can be checked in negligible time.

Answer 4

If the number to reach is not too large, you can probably generate all the reachable numbers from the set that fall in the range [1,N].

Problem: Reach N using the elements in the list L, where N is small enough not to worry about a vector of size N elements' size.

Algorithm:

• Generate a vector V of size N
• For each element l in the list L
  • For each reachable element v in V
    • mark all elements v + n*l in V as reachable