Finding combinations of numbers adding to a given sum

[MsBindy]

Here is my dilemma.  I have a large file of data...maybe a millions rows (I'm sure I can narrow this down).  One of the fields is a value.  I want to find combinations of records where the sum of the value equals a given number.  I don't have an example because I don't even know where to begin.

For example,  let's say I'm looking for $1,410.15 within the data set.  That amount could be made up of any number of records that net to $1,410.15.

Has anyone built anything for this type of scenario in Alteryx?  I've seen some stuff on the internet but it looks too advanced for me.

[MsBindy]

Good grief...that is not supposed to be the 'subject'....how do I fix that?....figured it out.

[NicoleJohnson]

Wow, this one feels like a super-challenge! If someone solves this, you would make my accounting department very VERY happy when it comes time to do reconciliations... :)

@MsBindycan you provide a couple clarifications?

1. Are the values only positive, or are there negative values as well? (Asking because if they're positive, then at least you can start out by removing any values greater than your final value)

2. Can it be any combination of values that reaches the desired amount? Or are you limited to 2 values, 5 values, etc.? (Asking because that might make it easier to resolve if you don't have to iterate for any infinite number of combinations).

[MsBindy]

haha....I am actually helping the accounting department!

1. Are the values only positive, or are there negative values as well?  Positive and Negative

2. Can it be any combination of values that reaches the desired amount? Any combination of numbers

[NicoleJohnson]

I thought that might be the case :)

This one feels a bit PhD level to me (definitely run across this before, and got nowhere with it), so I'm hoping some other wizard out there has already come across this before... maybe an iterative macro, or something to do with optimization tools? The issue might end up being scale - could come up with something that works for 100 records, but a million feels like it will be a computing drain...

[MarqueeCrew]

@MsBindy,

This question has been posed before.  While @NicoleJohnson might suggest a PHD requirement, I think that there are R libraries that might exist to handle the problem.  Of course these functions also include a MAXIMUM number of values to test with as well as bounding negative and positive numbers to include in the calculations.  

So for now Donna, I think that you'll want to use the Excel solver that gets you to the answer.  Maybe someone will take the challenge to program something for you.  I created a Z-Score calculator this morning, I am going to coast into the weekend.

Cheers,

Mark

[MsBindy]

Thanks,  I will play with that for a bit and then also coast into the weekend.

[Bob_Blackey]

Yes - this is computationally intimidating !  it depends if you just need to find one set of records which sum (not too bad) or all the possible combinations.

Example: the goal is $1,410.15. You could start at the first record (let's say $100.34) - then you would have to find a record = 1309.81 (1410.15 - 100.34), otherwise then consider all the remaining records that are less than 1309.81. For each one of those you'd have to again find a number which gives an exact sum or look at all the remaining records less than the difference.

Given the large # of records (1,000,000) it might be fairly easy to find one match since you would expect to have records at almost every cent value (This depends on the distribution of the values - a lot of things ending in .99 would be tricky).

Finding all the matches is where it sounds scary.

I'd be tempted to do this in R or Python instead of tools. 

Cheers,

Bob

[AmitMiller · Accepted solution]

could this help?

[MsBindy]

Very cool.   It looks like it works!  Thanks.