Suppose that you have a collection of records in a table. Each record contains a column which has a non-zero integer amount in it. The amount can be positive or negative.
You are given a target amount. Your job is to retrieve all records in the table whose amount matches the target amount given. However, it could be that the sum of (2 or more) records yield the target amount. The result set needs to identify all records (single or combination) that match the target amount.
This is not a homework problem, even though I recall doing something like this in college... but that was long ago. This actually has a real-life use in trying to find an error in an accounting log.
Does anyone know of an efficient algorithm (well, preferably not N!) for this problem? Or is this one of those hopeless scenarios...
For example:
Record 1: 10
Record 2: -2
Record 3: 12
Record 4: 2
Record 5: 6
Record 6: 8
Record 7: 3
Record 8: 1
Target: 10
Result set: Record 1, (Records 2 + 3), (Records 4 + 6), (Records 2 + 4 + 5 + 7 + 8), etc.
Enjoy!
Kevin
You are given a target amount. Your job is to retrieve all records in the table whose amount matches the target amount given. However, it could be that the sum of (2 or more) records yield the target amount. The result set needs to identify all records (single or combination) that match the target amount.
This is not a homework problem, even though I recall doing something like this in college... but that was long ago. This actually has a real-life use in trying to find an error in an accounting log.
Does anyone know of an efficient algorithm (well, preferably not N!) for this problem? Or is this one of those hopeless scenarios...
For example:
Record 1: 10
Record 2: -2
Record 3: 12
Record 4: 2
Record 5: 6
Record 6: 8
Record 7: 3
Record 8: 1
Target: 10
Result set: Record 1, (Records 2 + 3), (Records 4 + 6), (Records 2 + 4 + 5 + 7 + 8), etc.
Enjoy!
Kevin
