Isolate UNIQUE combination of Z cells from a range N that adds up

[alex]

I have a range of N cells, all in one column and all unique numbers. I also
know that Z cells from this range adds up to a number R. This combination of
Z cells is unique, i.e. there is only one combination of Z cells that adds up
to R.

How can I have these Z cells shown in a separate column? In other words,
how can I isolate them?

Thanks for any help!!!

 

[Sam Wilson]

It depends entirely on N and Z - there are N!/(Z!(N-Z)!) combinations which
for large N can quickly become problematic.

If Z is reasonably low you can nest loops - say Z=3

for i = 3 to N
for j = 2 to i
for k = 1 to j
'pick element i of N
'pick element j of N
'pick element k of N
'add these elements, see if it's right
next k
next j
next i

If you want Z to be variable, then you'll need to construct an array of size
Z with elements consisting of 1 or 0, and then switch these 1s and 0s off in
Binary sequence to find your target - but you could be talking days of
computation as there are 2^Z combinations.

 

[alex]

Thanks! This is along the same lines I was also thinking about, and N is
indeed usually large (in the thousands) but so is Z in most cases. As you
said and based on the formula for the number of possible combinations, the
larger the N the larger the number of combinations, yet the larger the Z the
less combinations available. In my case, this is usually quite balanced with
the Z being close to N for more than 50% of the time. In other words (N-Z)
is usually relatively small...

Two questions, if I may:
1) How can I convert your algorithm to an Excel function or macro to run
within a speardsheet? I looked at the SUMIF and COMBIN functions (and
others), but could not figure out how to make them work for my needs. Is
Visual basic or similar my only option?
2) Is there any way to calculate how long it will take to perform such a
calculation for a given N and Z on a "normal" home PC? For example, if I
know my processor speed, is it as straight forward as to calculate x
operations (where x is the number of possible combinations) versus the clock
speed of a computer (say 1.8 MHz etc)?

Thanks again!!
Alex

 

[Sam Wilson]

As a rough estimate of how long this would take, there are 2^N possible
combinations of N numbers - because there are N numbers the average number of
those combinations containing exactly Z of the numbers is (2^N)/N. To check
each of these (2^N)/N combinations you need to find and add Z numbers, so
that's Z*(2^N)/N computations. If Z and N are usually of the same magnitude,
that's effectively 2^N combinations.

Say N is a thousand. 2^N = 1.07 * 10^301. Say your home PC can do 1 million
computaions a second (it can't...) that means you need 1.07*10^295 seconds to
check these combinations

Probably not the answer you'd hoped for.