Finding out which combination of numbers equals $x

[jecasc]

I have the following problem:

I have a variable $x for example: 2138.25

I have several numbers in an array $numbers[]:
123.23
348.56
1435.33
702.92
744.95
...

Now I need to find out, which combination of the numbers equal $x. Problem is: How many of the given numbers equal $x is also a variable. Sometimes its a combination of two numbers, sometimes its three or four, or five.

So basically I have:
$x = a given sum
$numbers[] = an array of numbers where $y of them equal $x
$y = how many of numbers[] are needed to equal $x

Anybody could point me in the right direction on how to do this in PHP?

[jecasc]

[offtopic]Wow, Google has become fast. I searched for a solution in Google just now, and was delighted when it showed up a Search Result with exactly the question I had asked here a few moments ago. I clicked on the result and - ended up here. It was my own question already showing in the SERPS.[/offtopic]

[Frank_Rizzo]

At first I thought you would need to traverse pascal's triangle until a match is met. This will solve if any one number, or any two numbers .... any (arraylength) numbers equal $x

But I don't understand

$numbers[] = an array of numbers where $y of them equal $x
$y = how many of numbers[] are needed to equal $x

[jecasc]

What I mean is this for example:

numbers[] = array(4,8,2,35,67)
y=2 would mean that the sum of two elements in numbers[] equal the end result, y=4 would mean the sum of four elements of numbers[] is needed.

[tangor]

Gin!

[jecasc]

Gin!

Don't know if getting drunk will help me find a solution. But I'll try anyway. Thanks for the suggestion.

[tangor]

It is obvious you should not play Gin Rummy with me, jecac! But getting drunk from time to time might bring inspiration (most of which will be "Why did I do that?" and more importantly "What problem am I trying to solve?"

Your array and query make no sense TO ME. Need a bit more. And I am a number cruncher, hence the humorous "Gin!" remark.

[penders]

Once the hangover clears...

Do you expect only 1 solution with your data? What if there are multiple? eg.

$NUMBERS = array (1,2,3,4,5,6,7,8,9,10); 
$TARGET = 10; // Solutions: 10, 8+2, 7+3, 6+4, 7+2+1, ...

[jecasc]

Do you expect only 1 solution with your data? What if there are multiple?

If there are multiple solutions it would be best if I get all of them:
For example if I have:

$NUMBERS = array (5,23,43,411,9,11,34,87,4,12);
$TARGET = 39
$y = 3

Then I would expect the solutions:
5,11,23 and 4,12,23


For:
$NUMBERS = array (52,231,43,93,411,94,11,334,827,12);
$TARGET = 200
$y = 4
I would expect: 52,43,94,11 and 52,43,93,12

I know how I could do this if $y where a fixed value, for example $y = 2. Then I simply would use two nested "for" loops and try all combinations. However I don't know how to do it if $y is a variable.

[penders]

Ah, is $y a value you give to the function? ie. I want a solution with 4 values ($y = 4)?

Or (this is what I was assuming)... $y is returned from the function, indicating the number of values in the solution (although this is simply a count of the numbers in the solution and doesn't need to be calculated separately).

[jecasc]

Ah, is $y a value you give to the function? ie. I want a solution with 4 values ($y = 4)?

Yes, $y is not returned but a given variable. So $y=2 means I want to know which two numbers in $NUMBERS equal $TARGET, if $y=4 I want to know which four numbers in $NUMBERS equal $TARGET. Not up to four numbers but exactly four.

[Frank_Rizzo]

How large can $y be?

---

Rather than a card game this is more like lottery or horse racing combinations.

[azazello]

How big can your set grow?

As the size of your set grows the more difficult the problem becomes.

Take a look at :-

[stackoverflow.com...]

[en.wikipedia.org...]

[jecasc]

How large can $y be?

I guess that $y would normally be between 2 and 8 and normally there should not be more than 10 elements in $NUMBERS. Maybe I'll just write one function for $y=2, one for $y=3 and so on. This should be relatively easy to do. If $y is much bigger than 8 it will take too much time to process anyway.