c# – Brute force to solve refund amount in a payment/invoice domain

I work at a major Swedish insurance company. I’m in charge of a service that matches bank payments with invoices. I will not show the details of that match logic. But one outcome of the match is that amount on payment differs from amount on invoice. We have a IAmountDeviationStrategy that is tagged on each invoice. Here is the RefundStrategy

public class RefundStrategy : IAmountDeviationStrategy
{
    public AmountDeviationStrategy Strategy => AmountDeviationStrategy.Refund;

    public PaymentInvoiceMatchResult Execute(MatchJob job)
    {
        if (job.Diff < 0)
            return new PaymentInvoiceMatchResultBuilder(job)
                .PaymentCategory(PaymentCategory.WrongPayment)
                .RefundAll(RefundReason.UnderPaid);

        var invoiceAmount = Math.Abs(job.Invoice.Amount);
        var payingPayments = GetPaymentsComboClosestToInvoiceAmount(job.Payments, invoiceAmount);

        var refunds = job.Payments.Except(payingPayments).ToList();
        var result = new PaymentInvoiceMatchResultBuilder(job, refunds)
            .PaymentCategory(PaymentCategory.WrongPayment)
            .Refund(refunds);

        if (payingPayments.Sum(p => p.Amount) != invoiceAmount)
            result.Refund<RefundSplitPaymentCommand>(payingPayments.First(p => p.Amount >= job.Diff), split => split.Amount = payingPayments.Sum(p => p.Amount) - invoiceAmount);

        return result
            .QueueCommand(new MapInvoicePaymentsCommand { InvoiceId = job.Invoice.ExternalId, Payments = payingPayments.Select(p => p.ExternalId) });
    }

    private IReadOnlyCollection<IPaymentMatchInfo> GetPaymentsComboClosestToInvoiceAmount(IReadOnlyCollection<IPaymentMatchInfo> payments, decimal invoiceAmount)
    {
        var combos = Enumerable.Range(1, payments.Count)
            .SelectMany(i => new Combinations<IPaymentMatchInfo>(payments, new ReferenceCompare<IPaymentMatchInfo>(), i))
            .ToList();

        var payingPayments = combos
            .Where(c => c.Sum(p => p.Amount) >= invoiceAmount)
            .OrderBy(combo => Math.Abs(combo.Sum(p => p.Amount) - invoiceAmount))
            .First();

        return payingPayments;
    }

If the payment underpays the invoice we simlply refund the payment. If its overpaid the fun starts. There can be multiple payments. Most common is the customer have paid once and overpaid. Second most common is he have double paid, ie two payments which sums to 2x the invoice. Third and uncommon is multiple payments that overpays randomly (not double the amount).

Anyway, I bruteforce this problem. I find all combos of payments using a little Combination class https://pastebin.com/BDvRmmgD (Not written by me)

Once I have all combos I take the one combo closest to the invoice amount. I refund all others. I then check if the paying payments sum up to the amount (which they do in double paid scenario). If they dont sum up I split one of the payments and refund the overpaid part.

I then rerun the matching command MapInvoicePaymentsCommand. This time the invoice and payment will hit the Paid outcome path instead.

I think the brute force part is pretty elegant. There will never be more payments than a few so it will not be a performance problem.