find out if any combination of elements in the array sums to a specific size

Question

I am trying to find out if any combination of elements in the array sums to a specific size or not.

For e.g. input: {Sizes: [1,1,3,5], Goal: 2} output: Yes/No => Yes in this case as 1+1 = 2

One of the solutions i can think of is more of a brute force solution, where i will have n^2 tries to find a size specific to goal.

i.e. something like this :

for(i=0; i< array.size(); i++) {
    for(j=i+1; j< array.size(); j++) {
        if(i+j == goal) {
           return true;
        }
    }
}

is this the only approach ? also, is my code correct for the same ?

By 'combination', I don't mean 'pair' (must be exactly two items) but an actual combination (where it could be anywhere from 0 to all of the items)

Answer 1

This is a slightly stricter version of the Knapsack Problem. In short, there is no "best" way to solve it, as it is an NP-Complete problem.

If anyone has found a single optimal way to solve this problem, I encourage you to write a paper on it at once, submitting it to the ACM and IEEE, and enjoy your newfound wealth and fame.

I don't have any real experience with these sort of problems, but I did play around with genetic algorithms in college which are decently successful at this sort of thing. I'd give that a go, personally.

If you're dealing with data sets as small as are in your problem, you're probably best just brute forcing it. For a group of 5 numbers, there are at most 325 possible permutations, which wouldn't take too long to iterate through. Less time if you made common sense optimizations like neuronaut suggested in comments.

The upshot is that you have a relevant XKCD. Enjoy.