This sample contains implementations of the algorithms presented in Computing Partitions with Applications to the Knapsack Problem (Available for download here)

Details on how the algorithms function can be found in the paper. Basically all of them present different methods for enumerating all posible combinations. Feel free to add your own algorithm by implementing the SubsetSumStrategy and adding your algorithm to the unit test, you can see how it fares compared to the others.

You can run the the unit test with gradle test which will:

• Run a series of negative tests, no sum exists in the set.
• Run a series of positive tests, a sum exists in the set.
• Solve a specific instance of a puzzle.

It will output the running time in ms. of each algorithm. These algorithms can be very slow, particularly the naive approach, so be patient.

You can also run gradle eclipse and run the unit tests from within eclipse. Note that some of the algorithms require a lot of memory so your mileage may vary.

• It doesn't include any pseudo polyonomial or approximization strategies.
• Some algorithms could be improved by making use of heuristics, this is something still open for exploration.

Here are the worst case running times (i.e. no sum exists) for the various algorithms:

It looks like MultiSubsetSumStrategy2b is the winner here. The only drawback about this one is that it uses O(2^n) space..