Matching Payments To Invoice Groups

InvoiceMix solves a common reconciliation problem: a finance team receives one payment, deposit, or accounting total, but the payment may cover several invoices. The system needs to find every unique invoice group that exactly reaches the target amount without reusing the same invoice twice.

The full application supports manual entry, spreadsheet upload, saved scenarios, CSV export, min and max invoice counts, and required invoice IDs.

• Live demo
• Source code

Product Surface

The visual model above shows the product boundary: InvoiceMix turns messy finance inputs into a bounded subset-search workflow, then presents matches in a way finance teams can inspect or export.

The portfolio demo keeps only the core search model. The production app adds spreadsheet parsing, API validation, saved scenarios, CSV export, deployment, and UI workflows around the same problem.

Why This Is A Search Problem

The naive solution is to generate every possible invoice subset and test whether its total equals the target. That search space grows exponentially in the worst case, which becomes expensive quickly.

InvoiceMix makes the problem practical for normal finance workflows by applying guardrails and pruning:

1. Validate invoice IDs, amounts, target, and filters before searching.
2. Sort invoices by amount so branches can stop early.
3. Walk the search tree with backtracking.
4. Stop a branch when the next invoice is larger than the remaining amount.
5. Apply min, max, and required-ID filters before returning a match.
6. Cap request size and result count to avoid runaway searches.

Backend Design

The backend is a Spring Boot API with a focused service boundary:

CombinationController
  -> validates JSON or multipart upload requests
  -> calls CombinationService
  -> returns combinations, counts, and invoice amount lookup
 
ExcelInvoiceParser
  -> reads XLSX, XLS, CSV, and TSV inputs
  -> extracts invoice ID and amount columns
 
CombinationService
  -> sanitizes invoices
  -> enforces unique IDs and positive amounts
  -> runs the backtracking search

The important decision is that file parsing and combination search are separate concerns. Parsing turns messy finance exports into a clean list of { id, amount }; the search service only handles validated domain input.

API Shape

The JSON workflow sends a target, optional filters, and invoice rows:

{
  "target": 150,
  "minInvoices": 1,
  "maxInvoices": 3,
  "requiredInvoiceIds": ["INV-001"],
  "invoices": [
    { "id": "INV-001", "amount": 70 },
    { "id": "INV-002", "amount": 80 },
    { "id": "INV-003", "amount": 50 },
    { "id": "INV-004", "amount": 100 }
  ]
}

The response returns combinations by ID and a lookup table for display/export:

{
  "combinations": [
    ["INV-003", "INV-004"],
    ["INV-001", "INV-002"]
  ],
  "combinationCount": 2,
  "invoiceAmounts": {
    "INV-001": 70,
    "INV-002": 80,
    "INV-003": 50,
    "INV-004": 100
  }
}

Trade-Offs

The algorithm remains exponential in the worst case. That is honest and unavoidable for exact subset matching. The engineering work is about reducing practical cost and protecting the system:

• Request guardrail: maximum invoices per request.
• Result guardrail: maximum combinations returned.
• Domain filters: min invoice count, max invoice count, and required IDs.
• Early pruning: stop branches that cannot reach the target.
• Exact arithmetic: backend uses BigDecimal to avoid floating-point accounting errors.

What The Project Demonstrates

InvoiceMix is not only an algorithm exercise. It connects mathematical reasoning to a real finance workflow:

• Model an accounting problem as subset search.
• Turn NP-complete theory into a practical bounded tool.
• Separate parsing, validation, search, and presentation.
• Build a full-stack product around a narrow business pain.
• Preserve auditability through clear combinations and CSV export.

Future Improvements

The current roadmap includes custom column mapping, multiple worksheet support, locale-aware currency formatting, partial-match mode, progress and cancel support for large searches, and API authentication for production deployments.