Fascinating problem…

This can be solved by applying some simple rules and a recursive stored procedure.

First, I would decide to apply a rule that says we will apply the payments to the oldest invoices first. That means that to solve this, I would retrieve the account records for all open invoices into an internal temporary table in date order. This temporary table will be visible to the recursive procedure, and should contain (at least) a rownumber (e.g., 1..45), the invoice key (back to the main tables), the invoice amount (+ or -), and a “flag” column as to whether it is “involved” in the current solution attempt.

Unfortunately, if you have to allow for open invoices with negative (credit) amounts, that makes the recursion inefficient, as you essentially need to evaluate EVERY combination of open invoices, instead of stopping when the payment is less than the sum of the current set of invoices being evaluated.

*** NOTE *** in actually testing the following, realized a couple of important points:

1. SQL Server only allows 32 levels of recursion – ergo, if you have more than 31 open invoices for an account, this will fail. This probably isn’t a limiter, because of the next point.

2. Because of the need to evaluate ANY combination of open invoice amounts, the recursive approach below is an N-factorial solution. If you have 10 open invoices, this could require 3.6 Million evaluations, 20 open invoices and you are looking at 2 Quintillion evaluations. Effectively, any more than 10-11 open invoices will take too much time to evaluate.

3. If the payment was for a single invoice that was NOT the oldest, the recursive approach will unfortunately evaluate all combinations with the oldest invoice first. If you had 10 open invoices and the payment was for the second oldest, you will evaluate 9-factorial combinations before finding that it matches invoice #2′s amount.

4. If all else fails, consider implementing some form of partial payment processing – clear the oldest invoices forward until you run out of payment and stop, leaving the last one with a partial pay (or partial owe).

So – while the code below will work, a more efficient, but more complicated approach would be:

1. Try to match the payment against any single invoice amount. (Probably wins most of the time.)

2. Try to match the payment against any pair of invoices. This is much less than N-factorial. (Algorithm not provided – left as an exercise for the student!)

3. At this point, do the full recursive evaluation, BUT recognize that it will probably never finish if there are more than 10 open invoices. In this case, I would probably try getting the oldest 10 and giving up if it didn’t satisfy any combination of those.

<pre>create table #invoices (

ix int, — a local 1..n index for accessing records in this table

invoicepk int , — or whatever your primary key to your invoice table is

amt decimal(18,2), — to hold the invoice amount

isused bit — true if this invoice is “participating” in the solution, else false

);</pre>

The main procedure would take at least two arguments – Account number for the payor, and the payment amount. Depending on what else your system needs to do, it could either directly mark the records as paid, or be a table-returning function that returns the invoices to be cleared by the payment.

The procedure would retrieve all open invoices into the internal table, setting the “ix” field to 1..<count of record>, and resetting the “isused” bit to false.

Then, the body of the main procedure is as follows:

<pre>declare @i int;

declare @maxrow int;

declare @remamt decimal(18,2);

set @i = 1;

select @maxrow = max(ix) from #invoices;

set @remamt = <payment amount>

exec @result = myRecursiveProc( 1, @remamt, @maxrow );

if @result = 0

– then we found a solution

– at this point, the set of #invoices records with isused=1 is the answer

– return the list of invoice keys

select invoicepk from #invoices where isused = 1;

else

– oops – payment doesn’t match any combination of open invoices

select null;

end;</pre>

The recursive procedure is as follows:

<pre>create procedure myRecursiveProc (

@row int,

@remamt decimal(18,2),

@maxrow int

)

as

begin

declare @invamt decimal(18,2);

declare @locremamt decimal(18,2);

declare @nextrow int;

declare @result int;

— note – bail if the answer is ALREADY 0 here

if @remamt = 0

return 0;

update #invoices set isused = 1 where ix = @row;

select @invamt = amt from #invoices where ix = @row;

set @locremamt = @remamt – @invamt;

— now – three possibilities

— = 0, done, we found a solution

— <> 0 and @row < max(ix), not done, try the next invoice

— <> 0 and @row = max(ix), this solution cannot work, pop up and try a different combination

if @locremamt = 0

return 0; — yeeha! solved – done

if @row = @maxrow

begin

update #invoices set isused = 0 where ix = @row;

return -1; — nogo, pop-up and try another combination

end;

— call us to try with the remaining invoices

set @nextrow = @row + 1;

exec @result = myRecursiveProc @nextrow, @locremamt, @maxrow ;

if @result <> 0

begin

— unmark this record, try again

update #invoices set isused = 0 where ix = @row;

— try with remaining invoices, but with *original* remaining amount

exec @result = myRecursiveProc @nextrow, @remamt, @maxrow ;

end;

return @result; — doesn’t matter what result here, pop up and let next level deal

end;</pre>

There are more elegant ways to code this, but the logic above should be easy to follow.

## Discuss This Question: 7 Replies