Give list of numbers to determine which combination gives you a given value

Question

Ok so my programming skills are really novice and super rusty but here is my issue. I need a way to take a list of given numbers and add them together in all combinations to determine which combo equals a certain amount. My wife works at pepsi and they have to do this by hand and she asked me to help her out. i will be attempting this with c++ if possible. Thanks guys.

P.S. Here is the info i was given incase it helps. http://dl.dropbox.com/u/9609070/Photo/Pepsi.tiff

Answer 1

I went ahead and made a brute forcing thing. It'll get the job done if you leave it running for a long while, but definitely a lot faster than people. I used a list of integers to make it easier to test, so every int there should be a double.

#include <algorithm>
using std::accumulate;
using std::distance;
using std::includes;
using std::next_permutation;
using std::sort;

#include <fstream>
using std::ifstream;

#include <iostream>
using std::cout;

#include <vector>
using std::vector;

int main()
{
    const int wantedSum = 100; //this is your wanted sum here

    vector<int> v; //stores all of the numbers to choose from
    vector<vector<int>> matches; //stores combinations (no different ordering)

    ifstream inFile ("combination sum.txt"); //file to read values from

    int input;
    while (inFile >> input) //fill v with values
        v.push_back (input);

    inFile.close();

    for (vector<int>::size_type subSize = 1; subSize < v.size(); ++subSize) //go from 1 element at a time to the number to choose from
    {
        vector<int> sub (subSize); 
        sort (v.begin(), v.end()); //sort original vector

        do
        {
            for (vector<int>::iterator it = sub.begin(); it != sub.end(); ++it) //fill subvector with first n values in v
                *it = v.at (distance (sub.begin(), it));

            if (accumulate (sub.begin(), sub.end(), 0) == wantedSum) //check for sum
            {
                sort (sub.begin(), sub.end()); //sort subvector

                bool found = false; //check if same (but different order) as another
                for (const auto &element : matches)
                    if (includes (element.begin(), element.end(), sub.begin(), sub.end()))
                    {
                        found = true;
                        break;
                    }

                if (!found) //if it isn't the same as any
                {
                    matches.push_back (sub); //push sorted vector

                    cout << '{'; //output match

                    for (const auto &element : sub)
                        cout << element << ' ';

                    cout << "\b}\n";
                }
            }
        } while (next_permutation (v.begin(), v.end())); //go onto next permutation of v (this is what causes uber slowness as v's size grows)
    }
}

Input:

45
24
3
79
8
30
55
27
34
9

Output:

{45 55}
{3 8 34 55}
{9 27 30 34}
{3 9 24 30 34}

Execution time (yours will probably be higher): 0.840s

I'm not saying this is the best solution, but it works. Of course your list is quite large compared to the one I gave it so it will take a lot longer.

Oh, and some of this will take C++11 to compile. It might just be the ranged-for loops and the double right angle bracket. They can be fixed with

for_each (vec.begin(), vec.end(), some_func); //in algorithm

and

vector<vector<int> > v;

respectively. Cheers if this gets the job done in a reasonable amount of time.

Edit:

Replace for (const auto &element : sub)... with

for (vector<int>::const_iterator it = sub.begin(); it != sub.end(); ++it)
    if (includes (element.begin(), element.end(), sub.begin(), sub.end()))
    {
        found = true;
        break;
    }

It would be replaceable with std::for_each if it weren't for the fact that you need access to found inside, so it's back to an explicit loop.