Math formula question, does one exist for this?

[Joemonkey]

OK suppose I have x amount of numbers and a sum. I want to figure out all possible combinations of the x numbers that would equal that sum. Easy example:

x=5
numbers are: 2, 5, 7, 8, 10

sum=15
combinations are: 7,8 and 5,10 and 2,5,8

now suppose:

x=300
numbers are dollar amounts ranging from $2.50 to $30,000

sum=$48,584.13


is there a way to plug in all the x numbers and the sum and have a formula tell you all possible combinations?

 

[letdown427]

A formula to show you all possible combinations? No. Well, not that I am aware of. Just seems extremely unlikely, given how maths is.

Might be a way of finding how many possible combinations, but still...

 

[Joemonkey]

well maybe not a simple plugin formula, but maybe something written in C that takes all possible combinations and spits out the ones that work

 

[screw3d]

Originally posted by: Joemonkey
well maybe not a simple plugin formula, but maybe something written in C that takes all possible combinations and spits out the ones that work

I can imagine an algorithm that does this, but it's probably gonna take a while to run given the sheer number of combinations possible.

 

[BigJ]

You could definitely write an algorithm that does this, but to make it efficient and correct, it may take awhile.

 

[Joemonkey]

Originally posted by: BigJ
You could definitely write an algorithm that does this, but to make it efficient and correct, it may take awhile.

The only problem is I have no programming skills. You'd think someone somewhere would have an open source version, but I really don't know what search terms to use.

 

[notfred]

Originally posted by: Joemonkey

Originally posted by: BigJ
You could definitely write an algorithm that does this, but to make it efficient and correct, it may take awhile.

The only problem is I have no programming skills. You'd think someone somewhere would have an open source version, but I really don't know what search terms to use.

Why the heck would anyone have an open-source program to do this? It's a problem that is completely pointless to solve.

 

[tfcmasta97]

nPr and nCr on your calculator do this

nPr would give you all possible combinations without repitition of order, nCr gives you all possible combinations including repeated order
ie 2+1 and 1+2 only count as 1 for nPr but nCr counts that as 2 possible results

 

[bonkers325]

i believe linear programming is what you're looking for, but its not a clear cut formula and does take some time to set up unless you buy/download a program to do it for you

 

[QED]

Nope, there's no formula for that.

You can brute force it by checking each of the 2^300 possible partial sums. You can even optimize it a little by doing a recursive algorithm... but there is no simple formula.

 

[Joemonkey]

Originally posted by: notfred

Originally posted by: Joemonkey

Originally posted by: BigJ
You could definitely write an algorithm that does this, but to make it efficient and correct, it may take awhile.

The only problem is I have no programming skills. You'd think someone somewhere would have an open source version, but I really don't know what search terms to use.

Why the heck would anyone have an open-source program to do this? It's a problem that is completely pointless to solve.

right... that's exactly it, i want to solve this for sh!ts and giggles...

there's an issue where the one of our banks has a huge deposit listed, and someone here fvcked up how they deposited her checks, so now we have to figure out which of 100 small deposits equals the large deposit exactly.