How to determine if any combination of values combined will equal a target value?

[DamirH]

I am typing this on my phone so it might be messy. Basically what you want is a fairly advanced algorithm. What I have in mind is probably not the most optimal solution and I suggest poking around google for closest sum algorithms. Now…

You have 12 values and want to get a total of 500… You take an empty bucket (0) and start “pouring” your numbers in. First of all remove any numbers that are greater than 500. Then start with the largest one that fits and keep adding in smaller numbers until you either get 500 or the next number you add exceeds 500.

Now this is where you run into the problematic part. Question is now if you can replace any of the existing bigger numbers in your bucket with a combination of smaller ones to match 500.

Say for the sake of the argument that at this point you have 496 in your bucket so you need to add in 4 to complete it, but all of your remaining numbers are > 4.

First of all, you know that every number in your bucket is greater than every number outside since you added them in decreasing order. The first step is checking each number outside your bucket and seeing how much it would overshoot. Then, for each of those compare your other outside numbers with your bucket numbers and see if any of them is smaller by the overshoot amount. If it is then you can just swap them and your overshoot number will now fit perfectly.

This can be optimized somewhat by doing the “does the difference match the overshoot” check in increasing order, i.e. for each outside number start checking from the smallest bucket number and work upward to the largest one… Keep going as long as their difference is.smaller than the overshoot. If it… overshoots the overshoot you can move on to the next outside number.

Now, if THIS doesn’t yield the result there remains the possibility that by adding the outside numbers you can get one that fits in. This is where things get real tricky.

What you need to do is check is start adding up the outside numbers, run the whole thing from the top with the new sum being treated as one number. You do this recursively with each 2, 3, 4… n number addition of outside numbers.

Each iteration level should continue if their closest match is closer than the previous ones. It should return if the match is <= than the current best. If all the “additions” return then you can’t make your addition.

Now that I’ve typed it all out I do not believe this to be the most optimal solution. I’ll give it some more thought and get back to you.
EDIT:
Ok a small google search confirmed that this is essentially the knapsack problem. This is the solution:

There are several ways to solve subset sum in time exponential in N. The most naïve algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O(2NN), since there are 2N subsets and, to check each subset, we need to sum at most N elements.

A better exponential time algorithm is known which runs in time O(2N/2). The algorithm splits arbitrarily the N elements into two sets of N/2 each. For each of these two sets, it stores a list of the sums of all 2N/2 possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time O(2N/2N). However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time O(2k). Thus, each list can be generated in sorted form in time O(2N/2). Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to s in time O(2N/2). To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than s, the algorithm moves to the next element in the first array. If it is less than s, the algorithm moves to the next element in the second array. If two elements with sum s are found, it stops. Horowitz and Sahni first published this algorithm in a technical report in 1972.

An alternative solution and more info here: Subset sum problem - Wikipedia

Edit 2:
A code solution (both slow but simple and less slow but more complex) found here:Dynamic Programming - Subset Sum Problem