Getting all the simple combinations of n elements with a query (and what to do next)

Last week a colleague of mine came up with an entertaining problem:

which invoices, out of a set of 14, when added together, result in a certain total?

(image courtesy of T. Plesk)

I mean, in comparison with my average tasks, this was definitely an entertaining one.

Mathematically speaking the answer to the question turns out to be a practical application of simple combinations of n elements taken k at a time, whose formula is n ! / (k ! * (n - k)) !  where k ranges from 1 to n, which results in a total of 2^n-1 possibilities.

Now the question is: can I solve this using a relatively simple SQL query or do I need to write a procedure with all the bells and whistles?

And the answer is: yes, I can.

Of course there is a practical limitation on the maximum number of elements that can be processed because, as you can easily guess, 2^n-1 for n > 24 results in a pretty large data set. Moreover there is also the limitation of the maximum power of 2 that can be represented by Oracle, but that is sufficiently big to make the brute force calculation unpractical.

But with 14 elements, that is 16383 combinations, it's definitely affordable. 

with
  figures as (
    select id, figure as figure
      from list_of_values
     order by id 
  ),
  numbers as (
    select rownum as num
    from dual
    connect by level < power(2,(select max(id) from figures))
  ),
  totals as (
    select n.num, 
  --  listagg(case when bitand(n.num, power(2, f.id-1 )) = 0 then '0' else '1' end) within group (order by f.id) as binary_mask,
      listagg(case when bitand(n.num, power(2, f.id-1 )) = 0 then 0 else f.figure end, ' + ') within group (order by f.id) as sums,
      sum(case when bitand(n.num, power(2, f.id-1 )) = 0 then 0 else f.figure end) as total
      from numbers n,
           figures f
     where f.id = f.id
    group by n.num
    order by n.num
  )
select * from totals
 where total between :low and :high
 order by total;

1. list_of_values is the table containing the amounts of the invoices (or any other numerical entities for other purposes). Replace with any other table of your choosing but retain the same column names using aliases. The column ID must contain the natural numbers 1... N.
   But you can also supply the values on-the-fly using JSON_TABLE:

   with figures as (
     select
       id,
       figure
     from
       json_table ( '[10.35,21.2,333.78,41.9,57,20.9,42.01,10.11,9.98,5.02,5.67,0.05,1.43,2.76]' format json, '$[*]'
         columns (
           id     for ordinality,
           figure number path '$'
         )
       )
   ), ...

   
   
2. The first listagg function is commented out, but you can turn it on in case you wish to see the binary representation of "num".
   
3. The second listagg function shows you the expression corresponding to the sum of the current combination of values. If you have enabled the first listagg and you look carefully, you will see that the positions of the 0s in the binary number and in the expression are matching, whereas 1s stand where the actual values stand in the list.
   
4. low and high are bind variables that will filter out the results in the given range. Put the same value in both variables to look for a precise amount. The range of values may come in handy to compensate for little differences owing to round-offs: for instance you might be searching for which values amount to 1234.56 but the individual figures contain more decimal digits and the actual sum could be 1234.5678.
5. If there are more elements with the same value, the query will return several rows. Even more if you are searching within a range.
6. Note that we can use the same query if there are also negative numbers. In this case it could be used to find out if there are any combinations resulting into a total of zero. May be there is a practical application for this in some area.