How to use the subset sum reconciliation finder
- Enter the amounts, one per line, either as an amount or as a label, a comma and an amount.
- Enter the target total, for example the size of a bank deposit.
- Set an allowed difference if you want to accept near matches, such as 0.05, and choose how many matches to list.
- Read the number of combinations found and the first ones in the table.
Formula
amounts are converted to whole cents
depth first search over amounts sorted from large to small
keep a combination when |sum - target| <= allowed difference
The search adds amounts one at a time and drops a branch as soon as the sum passes the target or the amounts left cannot reach it. Each amount is used at most once.
A $100.00 deposit
Six invoices are listed: 45.50, 20.00, 34.50, 15.25, 60.00 and 39.75, and the deposit is 100.00. The only combination that reaches exactly 100.00 is Invoice 101 + Invoice 102 + Invoice 103 (45.50 + 20.00 + 34.50).
With an allowed difference of 0.25, the combination 60.00 + 39.75 = 99.75 is found as well, shown as 0.25 below the target. The total of all six amounts is 215.00.
Why a match is only a lead
More than one combination can add up to the same total, and a match by chance is common once the list is long. Use the combination as a lead and then check dates, customer names and reference numbers before you mark anything as paid.
The page shows every combination it finds up to the number you choose, so you can see whether the match is unique.
Limits on size and time
Finding combinations is hard in general, because the number of subsets doubles with every amount. The page reads up to 40 amounts and stops its search after a fixed number of steps. If that happens it says the count is a lower bound.
Amounts must be positive. To match a deposit made of invoices less a credit note, subtract the credit before you enter the amounts, or run the search on the invoices only.
Assumptions and limits
- Amounts are positive and have at most two decimals.
- Every amount is used at most once in a combination.
- The search stops after a fixed number of steps and says so if it does.
- The allowed difference is in the same currency as the amounts.
- Nothing you type is stored or sent anywhere.
Frequently asked questions
Can the same amount appear twice?
Yes, if you list it twice. Two lines with 20.00 are treated as two different items, so combinations using either line are counted separately.
Why does the count say "or more"?
The search stopped when it reached its work limit before it finished, so the true count may be larger. Reduce the list or allow no difference to narrow the search.
How are cents handled?
Each amount is turned into a whole number of cents before the search, so no rounding errors can make a true match look like a near miss.
Can I find the total with fees taken out?
Add the fee to the target first. For example, if a processor paid out 97.00 after a 3.00 fee, search for 100.00 on the gross invoice amounts.