I apologize in advance if my question is not appropriate for this forum, as it is primarily a question about algorithms rather than specific implementation in PL/SQL and/or Oracle SQL. (Although those matter too, of course.)
The subset sum problem is a classical, well-known and difficult combinatorial problem. https://en.wikipedia.org/wiki/Subset_sum_problem It has several more-or-less equivalent formulations; I am interested specifically in the following one:
We are given a set X of positive numbers (possibly with duplicates - that doesn't make the problem any harder) and a positive number N. We need to find a subset Y of X so that the sum of elements in Y is exactly N, or if no such subset exists, we need to know that information. If more than one such subset Y exists, we will be satisfied with one of them (it doesn't matter which one).
Example: X = {3, 8, 22, 40, 17, 32, 4} and N = 47. In this case the subset Y = {3, 4, 40} is good. So is Y = {8, 22, 17} but we don't care - as soon as we found ONE solution we may declare victory.
One way to approach this problem is to build all the possible subsets of X, compute the sum, compare to N. This is easy to understand and to code, but if the cardinality of X is C, then there are power(2, C) subsets, and this may get out of hand quickly.
The Wikipedia article I linked to above discusses several other approaches to this problem (in addition to the brute force approach of simply considering all the subsets). This morning I implemented in PL/SQL the Horowitz-Sahni algorithm described there; I find that it can handle, for example, a set X with 45 elements and find a subset with a given sum N (a specific value which is the sum of a subset of 15 elements) in about 30 seconds.
I am interested in other algorithms and/or implementations of those algorithms in PL/SQL.
In particular, @"Stew Ashton", in a different thread ( ) mentioned that he has a method that can find a number that is the sum of a subset of 20 elements out of a set X of 60 elements in 0.002 seconds. I would be very interested both in the algorithm and the implementation for that solution.
My original intent was to post my PL/SQL implementation of the Horowitz-Sahni algorithm in this thread, and ask for critique/suggestions for optimization etc.; however, if much better/faster methods exist, that would be a waste of everybody's time (not mine for developing it - I learned a lot of PL/SQL in the process - but that only benefits me).