### Epicor Reconciliation

A common task that most users perform. Some users find this task easy but it is very complicated.

In maths this problem is called the subset problem. It can be described as, given a set of integers or natural numbers, does any subset of them, sum precisely to the target amount. To an accountant this problem is described as reconciliation.

Generally reconciliations are performed to confirm all transactions are present in two accounts. A high level matching of total’s will normally suffice.

### But what if the totals don’t match?

The complexity of this problem is relative to the difference between the two total’s. The lower the variance the more complex the problem. If the number we are trying to match is very small an exhaustive search is the most practical solution. Checking every possible combination until we find a match.

There are several ways to solve a subset sum problem. The easiest would be to cycle through all the subsets of numbers and check if they match the value you are looking for. Excel is quite good at this, but human intervention is always required, and it could take a while if it’s a large population and the variance is small.

### How long should it take to reconcile a set of numbers?

The running time is of order *O (2N N) *. Which means the time grows exponentially with the complexity. Which means we could be waiting days for an answer if the number sets are large and the variance is small.

This problem lends itself to an algorithm that can be left to crunch the numbers and get back to you when it’s found the result.

### How would you solve this problem with code?

To solve the problem in pseudo-polynomial time we use dynamic programming.

Pseudo logic as follows

if (A [ i ] > j)

DP [ i ] [ j ] = DP [ i – 1 ] [ j ]

else

DP [ i ] [ j ] = DP [ i – 1 ] [ j ] OR DP [ i – 1 ][ sum – A [ i ] ]

1. This means that if the current element has a value greater than the ‘current sum value’ we will copy the answer for previous cases.

2. If the current sum value is greater than the ‘nth’ element we will see if any of the previous states have already experienced the sum = ’j’ or any previous states experienced a value ‘ j – A [ i ] ’ which will solve our purpose.

set [] = { 3 , 4, 5, 2}

target = 60 1 2 3 4 5 6

0 T F F F F F F

3 T F F T F F F

4 T F F T T F F

5 T F F T T T F

2 T F T T T T T

Contact us if you’d like to learn more about our epicor reconciliation solutions.