# Most efficient way to solve the subset sum problem in PostgreSQL

I'm looking now at the subset sum problem... inspired from this post.

It's an interesting problem.. Here we create two tables

1. `foo` with 1,000 rows (id,rand) between 5..105
2. `bar` with 10 rows (id,rand) between 1..1,000

Source code to generate them is as follows.

``````CREATE TEMP TABLE foo
AS
SELECT x AS id,
trunc(random()*100)+5 AS rand
FROM generate_series(1,1000)
AS t(x);

CREATE TEMP TABLE bar
AS
SELECT x AS id,
trunc(random()*1000) AS rand
FROM generate_series(1,10)
AS t(x);
``````

Now the goal is to find whatever combinations of `foo` sum closest to the row in `bar` without going over.

Ideally, I'd like something like this.

``````bar.id  bar.rand   foo.ids              foo.sum
1       872        {14,398,72,...etc}   868
``````
• m! / (n! · (m-n)!) should it calculate the sum of all possible combinations of foo.id ? – McNets Feb 14 '17 at 22:43
• I am not sure at all that this is the kind of problem that can be solved in a close-to-optimal manner by using SQL. This is normally the kind of problem that can be solved using some kind of tree approach, and pruning (or not exploring) branches you already know will not comply, or whose result will be worse than the best that you've already checked through the leafs. You can do trees with recursive-CTEs... But I don't have any idea about how to something equivalent to pruning them. – joanolo Feb 15 '17 at 0:01