select invoiceID, amount, customerID from invoices

We receive payments from our customers that not necessary cover all the open invoices but might for some reasons exclude some of them. The only information is the total of that payment, lets say: total_Sum

Can you imagine a query that returns those invoices?

Select invoiceID where SUM(amount) = total_Sum

- somehow it has to check all possible combinations and see if any of them fulfills the request that the sum matches the total paid. Off course theoretically there might be more than one results of set of records returned, but this usually never happens. There can be up to 100 open invoices for one customerID

something like below assuming invoices will be closed in order of creation for customer to avoid ageing

SELECT i.invoice
FROM invoices i
CROSS APPLY (SELECT SUM(amount) AS CumulativeTotal
FROM invoices
WHERE invoiceid < = i.invoiceid
AND customerid = i.customerid
AND status = 'open'
)i1
WHERE i.status = 'open'
AND i1.CumulativeAmount <= @CustomerAmount
AND CustomerID = @CustomerID

I'm also assuming you'll have a field to indicate open invoices (say status) and CustomerID and their payment amount will be sent as input.

Thank you for your reply. If I apply your query to my testdata:

invoiceID amount customerid status
-----------------------------------
FCT001 3 1 open
FCT002 8 1 open
FCT003 5 1 open
FCT004 4 1 open

SELECT i.invoiceID
FROM invoices i
CROSS APPLY (SELECT SUM(amount) AS CumulativeTotal
FROM invoices
WHERE invoiceid < = i.invoiceid
AND customerid = i.customerid
AND status = 'open'
)i1
WHERE i.status = 'open'
AND i1.CumulativeTotal <= 17
AND CustomerID = 1

.. FCT001, FCT002, FCT003 is returned. The sum is 16 and not 17! The query should detect FCT002, FCT003, FCT004

Not understanding your query completely, I didn't manage to adapt it so that the correct result is returned. Anyway you seem on the right track.

Thank you for your reply. If I apply your query to my testdata:

invoiceID amount customerid status
-----------------------------------
FCT001 3 1 open
FCT002 8 1 open
FCT003 5 1 open
FCT004 4 1 open

SELECT i.invoiceID
FROM invoices i
CROSS APPLY (SELECT SUM(amount) AS CumulativeTotal
FROM invoices
WHERE invoiceid < = i.invoiceid
AND customerid = i.customerid
AND status = 'open'
)i1
WHERE i.status = 'open'
AND i1.CumulativeTotal <= 17
AND CustomerID = 1

.. FCT001, FCT002, FCT003 is returned. The sum is 16 and not 17! The query should detect FCT002, FCT003, FCT004

Not understanding your query completely, I didn't manage to adapt it so that the correct result is returned. Anyway you seem on the right track.

thats not correct it wont be able to pay FCT004 in full so how can that be returned in output? you mean you need to consider partial payment as well? ie like

SELECT i.invoiceID
FROM invoices i
OUTER APPLY (SELECT SUM(amount) AS CumulativeTotal
FROM invoices
WHERE invoiceid < i.invoiceid
AND customerid = i.customerid
AND status = 'open'
)i1
WHERE i.status = 'open'
AND COALESCE(i1.CumulativeTotal,0) < @CustomerAmount
AND CustomerID = @CustomerID

We have this open invoices to be paid by our customers. Sometimes they do pay us without referring to the invoiceID and if they do cumulative payments, having more than one invoice open, we just see the total amount that had been transferred, and so we have to guess and calculate various combinations in order to find out which invoiceID's actually must have been included in this payment.

We have this open invoices to be paid by our customers. Sometimes they do pay us without referring to the invoiceID and if they do cumulative payments, having more than one invoice open, we just see the total amount that had been transferred, and so we have to guess and calculate various combinations in order to find out which invoiceID's actually must have been included in this payment.

That I understood. But my question is in cases where remaining amount after applying to some invoices is not sufficient to pay any of the remaining invoices in full, do you still go ahead and apply residual amount partially on an invoice (ie pay 1 against invoice FCT004 having 4 as required amount) and report it in result? If yes, wont my last suggestion suffice?

Partial payments on an invoice do not occur! Our customer pays exactly the sum of the invoices he is paying! OK?! He just does not let us know which invoices he is paying. Accountancy needs to know which invoices had been paid in order to change status. In order to find this out I need this query.

Check all imaginable combination of payments done by the customer. Calculate the sum for each of these combinations and return that combination of invoiceID's where the total matches exactly the money that has been transferred to us by that customer.

This is all. Your concern on insufficient amount to pay remaining invoices makes me doubt that I made my point clear. The invoices excluded by this payment still remain "open", while the others will be closed. Regards, Martin

Partial payments on an invoice do not occur! Our customer pays exactly the sum of the invoices he is paying! OK?! He just does not let us know which invoices he is paying. Accountancy needs to know which invoices had been paid in order to change status. In order to find this out I need this query.

Check all imaginable combination of payments done by the customer. Calculate the sum for each of these combinations and return that combination of invoiceID's where the total matches exactly the money that has been transferred to us by that customer.

This is all. Your concern on insufficient amount to pay remaining invoices makes me doubt that I made my point clear. The invoices excluded by this payment still remain "open", while the others will be closed. Regards, Martin

I understood your explanation. But my question is do you've an ageing concept for invoices? ie time elapsed since invoice was raised? As per that you need to make sure earliest invoices should get closed first in same sequential order and will have logic to notify customers of cases where invoices are pending after certain period. If you just determine best combination and try to close the invoices from paid amount, you may end up picking invoices which are open out of sequential order and will end up leaving behind intermediate invoices without closing down. After some days those invoices will hit their "wait time" limit and system will raise notifications to customers who would have expected you to close the earliest invoice down with payment made rather than applying them to later ones. Thats why i gave logic based on sequential order in which they're raised. So far as customer payment correctly matches cumulative value for group of invoices you're fine

Yes, we have something that is an ageing concept. These tables are the tables behind the ERP and there are columns like duedate, createddate, status, ... but this is not relevant here. Unfortunately there is no influence from our side on the payment habit of our customer. Whether we want him to pay the earliest first or stick to a sequential order, he would not follow this.

Visakh, it's not about us paying our bills, but all about our customers that had paid us some amount of money! Therefore there is no best combination that we choose, but us trying to understand what invoices the customer had chosen to pay.

This is getting funny, as I really don't understand why I can't make my point clear and your questions confuse me as I can't see any relevance.

Yes, we have something that is an ageing concept. These tables are the tables behind the ERP and there are columns like duedate, createddate, status, ... but this is not relevant here. Unfortunately there is no influence from our side on the payment habit of our customer. Whether we want him to pay the earliest first or stick to a sequential order, he would not follow this.

Visakh, it's not about us paying our bills, but all about our customers that had paid us some amount of money! Therefore there is no best combination that we choose, but us trying to understand what invoices the customer had chosen to pay.

This is getting funny, as I really don't understand why I can't make my point clear and your questions confuse me as I can't see any relevance.

Martin

Sorry my point was not on customer following an order in closing invoices. My point was that we need to follow FIFO order while applying payments to invoices to avoid the agaeing issue. Reason is in one of projects we had an issue in logic which tries to apply payments against invoices which caused it to close invoice out of sequential order in which they were generated. The caused notifications to be passed to customers who thought they'd done payments to clear off the invoices which reached the limit. So suggestion given to use was to apply and close earliest open invoices with payment received and notify them only cases where there are invoices that still remained not fully paid and have reached their ageing period. Reading your explanation I got confused by this

somehow it has to check all possible combinations and see if any of them fulfills the request that the sum matches the total paid

No problem! :) But now that you found out what my question was about, do you think that it is possible?

Yep...Based on FIFO sequencing you can do like below

SELECT i.invoiceID
FROM invoices i
OUTER APPLY (SELECT SUM(amount) AS CumulativeTotal
FROM invoices
WHERE invoiceid < i.invoiceid
AND customerid = i.customerid
AND status = 'open'
)i1
WHERE i.status = 'open'
AND COALESCE(i1.CumulativeTotal,0) < @CustomerAmount
AND CustomerID = @CustomerID

I receive a payment of customer 1 of 17€ without knowing what he is actually paying me, because he has several invoices open. After calculating every of the possible 15 combination of invoices:

I come to the conclusion that the customer must have paid me FCT001, FCT003, FCT004. This is just an example with test data; one could imagine several results for a particular payment (e.g. 8 can be achieved or by FCT001 or by FCT002, FCT003) In real life the numbers are very complex which makes it very unlikely to get more than one match.

Can someone think of a query that returns the invoiceID for a given @payment?

Here is a solution that will match up each received payment to a combination of at most three invoices. You can extend the mechanism I described to work for combinations comprised of more invoices. I am sure someone will post a more efficient and perhaps more general approach.

DECLARE @Temp TABLE (tableinvoiceID VARCHAR(10), amount int, customerid int);
INSERT INTO @Temp VALUES
('FCT001', 1, 1),
('FCT002', 2, 1),
('FCT003', 3, 1),
('FCT004', 4, 1),
('FCT005', 5, 1),
('FCT006', 6, 1),
('FCT007', 7, 1),
('FCT008', 8, 1);
DECLARE @AmountRecieved INT = 8;
;WITH CTE AS
(SELECT tableinvoiceID, amount, customerid FROM @Temp
UNION ALL
SELECT 'EMPTY' as tableinvoiceID, 0 amount, 1 customerid ), -- ADD AN EMPTY INVOICE TO ALLOW SINGLE INVOICE TO BE INCLUDED IN THE SELECTION
CC1 AS
(SELECT *
FROM CTE T
CROSS APPLY (SELECT amount as SecondInvoiceAmount, tableinvoiceID as SecondInvoiceID, (amount+T.amount) as C2Sum from CTE
WHERE T.tableinvoiceID <> tableinvoiceID) T2
CROSS APPLY (SELECT amount as ThirdInvoiceAmount, tableinvoiceID as ThirdInvoiceID, (amount+T2.C2Sum) as C3Sum from CTE
WHERE T.tableinvoiceID <> tableinvoiceID) T3
),
CC3 AS
(SELECT ROW_NUMBER() OVER(PARTITION BY customerid order by amount) as RN, * FROM CC1 T where C3SUm = @AmountRecieved )
SELECT tableinvoiceID as FirstInovice, amount as FirstInvoiceAmount, SecondInvoiceID, SecondInvoiceAmount,
ThirdInvoiceID, ThirdInvoiceAmount, C3Sum As TotalAmount FROM CC3 T
WHERE
tableinvoiceID NOT IN (SELECT SecondInvoiceID from CC3 WHERE RN < T.RN and ThirdInvoiceID = T.ThirdInvoiceID) and
tableinvoiceID NOT IN (SELECT ThirdInvoiceID FROM CC3 WHERE RN < T.RN and SecondInvoiceID = T.SecondInvoiceID) and
SecondInvoiceID NOT IN (SELECT ThirdInvoiceID FROM CC3 WHERE RN < T.RN and tableinvoiceID = T.tableinvoiceID)
and ((tableinvoiceID = 'EMPTY') OR (tableinvoiceID <> ThirdInvoiceID))
and ((ThirdInvoiceID = 'EMPTY') OR (SecondInvoiceID <> ThirdInvoiceID))
and ((SecondInvoiceID = 'EMPTY') OR (tableinvoiceID <> SecondInvoiceID))
ORDER BY RN

EDITED: Added comments and renamed columns for clarity

Oooh. That was really fun - thanks. Try this. Not elegant and does not go beyond 12 eligible invoices. You do realise though that you can rapidly grow the combinations so you might want to further limit the candidates.

DECLARE @Temp TABLE (tableinvoiceID VARCHAR(10), amount int, customerid int);
INSERT INTO @Temp VALUES
('FCT001', 10, 1),
('FCT002', 2, 1),
('FCT003', 31, 1),
('FCT004', 42, 1),
('FCT005', 54, 1),
('FCT006', 61, 1),
('FCT007', 75, 1),
('FCT008', 18, 1);
declare @invAmount int=54;
declare @custID int=1;
with CombinationsThatMakeUpTotal as
(
select *
from
(
select
*,
SUM(amount) over(partition by num) sumOfCombo
from
(
select number+1 num from master.dbo.spt_values where type='p'
) combos
inner join
(
select power(2,row_number() over(order by tableinvoiceID)-1) invOrdinal,* from @Temp
where amount<=@invAmount and customerid=@custID
) invoicesWithOrdinal
on ((combos.num & invOrdinal)<>0)
) AllCombosSummedUp
)
select distinct /* now stuff it into one line and remove the duplicates */
stuff((
select ', ' + tableInvoiceID+': $'+convert(varchar(10),amount)
from CombinationsThatMakeUpTotal t2
where CombinationsThatMakeUpTotal.num = t2.num
for xml path(''), type
).value('.', 'varchar(max)'), 1, 1, '') [values]
from CombinationsThatMakeUpTotal
where sumOfCombo=@invAmount
group by CombinationsThatMakeUpTotal.num

@MuMu88: Thank you for this solution; it really does the job, but it is quite laborious to extend in order to make it work with more invoices.

@LoztInSpace: This is awesome! I am staring at this code for quite a while now, but can't retrieve any logic from it - but it works!!! And I liked especially that you enjoyed writing it. Unfortunately I can't see where the limitation to 12 invoices derives from; your comment on the growing number of combinations does not affect me, as the figures are usually rather complex and singular and I do not expect more than one match.

I am still playing with the query in order to find out more details on behavior, changing bits to understand how this is working. It seems to detects the right combination, but only considering the first 11 invoices, although you can add as many as you want. Hopefully someone can take this somewhat further, because it works like charm and is fast too

Hi Barnabeck, I apologise for not putting comments in - I agree it's not particularly easy to follow. The key to the limit (which is 11 not 12) is this bit:

select number+1 num from master.dbo.spt_values where type='p'

You can extend the limit by getting more numbers from somewhere but this runs out at 2048. The limit is this power of 2. Don't worry too much though - this is the total invoices outstanding by each customer (that's <= the amount they paid) so unless you've got very slack customers it might not matter! Of course you'll want to filter out only the unpaid invoices for this.

The combinations grow quite large though. Another 5 invoices and you need 64,000 rows. It will work though.

I started to explain fully but my ride is here so have to go. If you haven't worked it out by next Monday let me know and I'll write it up.

Hi Barnabeck, I apologise for not putting comments in - I agree it's not particularly easy to follow. The key to the limit (which is 11 not 12) is this bit:

select number+1 num from master.dbo.spt_values where type='p'

You can extend the limit by getting more numbers from somewhere but this runs out at 2048. The limit is this power of 2. Don't worry too much though - this is the total invoices outstanding by each customer (that's <= the amount they paid) so unless you've got very slack customers it might not matter! Of course you'll want to filter out only the unpaid invoices for this.

The combinations grow quite large though. Another 5 invoices and you need 64,000 rows. It will work though.

I started to explain fully but my ride is here so have to go. If you haven't worked it out by next Monday let me know and I'll write it up.

Great that you guys do have fun too... kind of nerdy doing this on a Saturday night!

Well, thinking about that problem again I was hitten by enlightenment, and realized something that really is fascinating me since then; I might have reinvented the wheel, but if this is the case, I hadn't had the slightest idea about its existence...

Sorry if I stepped on something trivial, but its not that trivial to me:

The key thing is, that all possible combinations [power(2,n)-1] for n-invoices are perfectly resembled by the numbers from 0 to power(2,n)-1 in binary. Every digit representing one invoice, where 1 meaning that an invoice has to be counted, while 0 is excluding it from a combination.

Each single digit from that number in binary (from right to left) is retrieved through this loop:

WHILE @Number <> 0
BEGIN
SET @BinDigit = @Number % 2
SET @Number = @Number / 2
END

I can directly use that 0/1 value as the factor for the summing up of the total for that combination. I check every total against the @payment. If there is a match, I rerun that same loop to get the invoices in the same way.

Although I hoped I could go beyond the limit of LoztInSpace' solution -you wont believe, but there are customers that have even more than a 100 open invoices- I see that the limit still is that same power of 2, that for some reason can't get beyond what is an equivalent to a 32 binary number, or 32 invoices; so this will do the job for 90% of our customers.

declare @invoices nvarchar(200)
declare @n int
declare @total real
declare @number int
declare @combi int
declare @Payment real
set @Payment = 27
set @combi = power(2,(select MAX(id) from OpenInvoices))-1
while @combi <> 0
Begin
set @number = @combi
set @total =0
set @invoices =''
set @n = 1
while @number <> 0
Begin
set @total = (Select amount * (@number % 2) from OpenInvoices where ID = @n) + @total
set @n = @n + 1
set @number = @number /2
END
IF @total = @Payment
Begin
set @number = @combi
set @n = 1
while @number <> 0
Begin
set @invoices = @invoices + COALESCE((Select invoiceid + left(' ', NULLIF (@number % 2,0)) from OpenInvoices where ID = @n),'')
set @n = @n + 1
set @number = @number /2
END
select @total,@invoices
END
set @combi = @combi - 1
END

How could I make this query return one table in order to pass it through .net sqldatasource?

quote: ... that for some reason can't get beyond what is an equivalent to a 32 binary number, or 32 invoices;

The reason you cant go beyond 32 invoices is that you are using INT as a data type for all your variables. INT is a 32 bit value (4 bytes). If you use BIGINT which is a 64 bit (8 bytes) value (as shown in Blue below), you can go up to 64 invoices, but the performance is going to be horrendous.

quote: How could I make this query return one table in order to pass it through .net sqldatasource?

A way to create a table is shown in red below:

DECLARE @Temp TABLE (ID BIGINT, invoiceid VARCHAR(10), amount int, customerid int);
INSERT INTO @Temp VALUES
(1, 'FCT001', 10, 1),
(2, 'FCT002', 2, 1),
(3, 'FCT003', 15, 1),
(4, 'FCT004', 42, 1),
(5, 'FCT005', 52, 1),
(6, 'FCT006', 61, 1),
(7, 'FCT007', 75, 1),
(8, 'FCT008', 18, 1),
(9, 'FCT009', 10, 1),
(10, 'FCT0010', 2, 1),
(11, 'FCT0011', 15, 1),
(12, 'FCT0012', 42, 1),
(13, 'FCT0013', 52, 1),
(14, 'FCT0014', 61, 1),
(15, 'FCT0015', 75, 1),
(16, 'FCT0016', 18, 1);
declare @invoices nvarchar(200)
declare @n bigint
declare @total real
declare @number bigint
declare @combi bigint
declare @Payment real
set @Payment = 70
set @combi = CAST(power(CAST(2 as bigint),(select MAX(ID) from @Temp))-1 as bigint)
CREATE TABLE dbo.Temp101(InovoiceTotal REAL, Invoices VARCHAR(MAX));
while @combi <> 0
Begin
set @number = @combi
set @total =0
set @invoices =''
set @n = 1
while @number <> 0
Begin
set @total = (Select amount * (@number % 2) from @Temp where ID = @n) + @total
set @n = @n + 1
set @number = @number /2
END
IF @total = @Payment
Begin
set @number = @combi
set @n = 1
while @number <> 0
Begin
set @invoices = @invoices + COALESCE((Select invoiceid + left(' ', NULLIF (@number % 2,0)) from @temp where ID = @n),'')
set @n = @n + 1
set @number = @number /2
END
INSERT INTO dbo.Temp101 select @total,@invoices
END
set @combi = @combi - 1
END
SELECT * FROM dbo.Temp101;
DROP TABLE dbo.Temp101