Agrupando números com base na soma mais próxima de um valor específico com o Postgres

Um pouco de pesquisa revela que essa questão é conhecida como o problema da soma do subconjunto em ciência da computação.

No stackoverflow, Lukas Eder fornece uma solução Oracle para uma pergunta semelhante e uma análise mais longa no blog do jooq.

Aqui está uma versão postgres derivada de seu trabalho:

CREATE TABLE tab(v text, c int);

-- populate table
INSERT INTO tab(v,c) VALUES('Z', 217);
etc...

-- show 10 better results

WITH RECURSIVE sums (subset_sum, max_v, a) AS (
        SELECT
            c,v,array[v] as a
        FROM
            tab

        UNION ALL

        SELECT
            c + subset_sum,
            v,
            array_append(a, v)
        FROM
            sums
        JOIN
            tab
        ON sums.max_v < tab.v
    )
SELECT subset_sum, a FROM sums WHERE subset_sum <= 60000
ORDER BY 60000-subset_sum
LIMIT 10;

O resultado com os dados de amostra é:

 subset_sum |      a      
------------+-------------
      59985 | {A,K,N,O,U}
      59985 | {I,K,R,T,U}
      59985 | {A,G,J,N}
      59985 | {A,F,G,P,Y}
      59985 | {C,K,O,Z}
      59985 | {A,C,F,J,O}
      59985 | {F,H,L}
      59985 | {D,E,M}
      59985 | {A,C,K,U}
      59985 | {E,J,K,M,R}
(10 rows)

Observe que o tempo de execução aumentará exponencialmente com a contagem de linhas na tabela base.