Sum a sequence of integers in a vector

Question

I have the function bool exists(int sum, vector<int>& vec) What it does is to return whether there is any sequence of numbers in vec that equals sum.

e.g

Vec = 140 80 90 180 70 sum = 300

The function returns true because the sequence 140 90 70 exists and equals 300.

For now i have the code:

bool possible(int sum, vector<int> &vec)
{
do
{
    int s = 0;
    for (int i = 0; i < vec.size(); i++)
    {
        s += vec.at(i);
        if (s == sum)
        {
            return true;
        }

    }
}while(next_permutation(vec.begin(), vec.end()));

return false;
}

It works but takes too long even when the vector size is just 20.

Can anyone help me with a better approach?

Answer 1

It works

First, it does not quite work, unless vec is sorted to begin with. Otherwise, next_permutation(...) would produce false without exhausting all possibilities, possibly skipping the permutation in which the right solution would be found.

but takes too long even when the vector size is just 20.

That's because this is an O(N!) solution. Note that N! is unnecessarily high even for a brute force solution, because the order in which you do additions does not matter. All you need is O(2^N) to try all subsets.

You can do better by employing a pseudo-polynomial solution to 0/1 knapsack problem. The idea is to create a set of all possible sums up to the desired number N. Start the set with a single number, zero. The on each iteration produce another set with contains all elements of the set from the previous iteration, plus the set produced by adding a number from your list to each of the previous sums, limiting the values at your target number (i.e. 300):

{ 0 }
{ 0, 140 } -- Added 0+140
{ 0, 80, 140, 220 } -- Added 0+80, 140+80
{ 0, 80, 90, 140, 170, 220, 230 } -- Added 0+90, 80+90, 140+90; 220+90 > 300, so it is not added
... // And so on

At the end of this process you would have all possible sums in the set. Now all you need to do is to check if your target number is present among the items in the set.