Which numbers add up to total? (2): Multiple Solutions 12

Note to readers: this post has been updated due to the inclusion – at the request of Torstein – of a further version of this solution, in which the number of values to be considered is dynamic and so may be set by the user. This version may be found at the very end of this post.

This post, inspired by a question from Patrick MacKay, from Belgium – thanks, Patrick! 🙂 – is a (rather belated) follow-up to that which I made here, in which, to recap, I presented a formula-based set-up which, given a target figure plus a series of values, determined which, if any, combination of those values had a sum equal to the target.

The only slight drawback to that solution was the caveat that, if more than one combination of values existed which satisfied that condition, then only one of those combinations was given.

Here I would like to improve upon that set-up by presenting a refined version which will return all such combinations. What’s more, at the very end of this deconstruction I will give a further version of the solution in which the number of values to be considered is a variable which may be set by the user.

In fact, that early post was also one of the very few in which I did not give an explanation as to how the solution works, which I would like to do here.

As an example of the output, imagine that our target value – £1054.35, for example – is here in A1, and that we have a list of 10 values in A2:A11, as below:

Which Numbers Add Up To Total (Multiple Solutions)

(You can download the workbook here.)

Columns B to K represent the (up to 10) solutions, indicated by an “X” appearing next to one of the 10 values in A2:A11 if that value forms part of a combination of those values whose sum is equal to the value in A1. Here it can easily be verified that there are 3 such solutions, since each of:

=350.25+246.89+457.21
=290.27+123.69+198.56+201.35+240.48
=283.75+290.27+123.69+201.35+155.29

does indeed give 1054.35.

Before I begin, it is worth reiterating the limitation inherent in this solution due to the resource-heavy nature of the formula-work involved. The set-up has a theoretical limit on the size of the dataset of 20 values. However, it is more than likely that Excel will run out of resources in that case due to the sheer size of the calculations involved. Indeed, 15 appears to be an approximate upper bound on the number of values to be considered using this set-up: any more than that and Excel may begin to struggle, and so readers hoping for a solution with a dataset of such a size should probably seek a VBA-based solution instead.

The required solution is as follows: first we go to Name Manager and define:

Values as:

=$A$2:$A$11

Arry1 as:

=ROW(INDIRECT("1:"&ROWS(Values)))

Arry2 as:

=ROW(INDIRECT("1:"&2^ROWS(Values)))

The array formula** in L1, which determines the number of permutations of summations which meet our target value (and so can be referenced in our main formulas so as to avoid resource-heavy IFERROR approaches), is:

=SUM(N(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=A1))

And the array formula** in B2 is then:

=IF(COLUMNS($A:A)>$L$1,"",IF(INDEX(INDEX(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),SMALL(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1,Arry2),COLUMNS($A:A)),),ROWS($1:1)),"X",""))

and copied to the right and down.

How does it work?

Let’s take one of the formulas which results in a positive return (i.e. results in an “X”) in order to see how this construction operates. Taking the formula in B5, for example, i.e.:

=IF(COLUMNS($A:A)>$L$1,"",IF(INDEX(INDEX(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),SMALL(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1,Arry2),COLUMNS($A:A)),),ROWS($1:4)),"X",""))

(Clearly the only part having changed being the reference being passed to the ROWS function.)

Let’s have a look in detail at this part:

MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2)

since this construction forms the crux of the solution.

In order to understand the functioning of this composition, it will be useful to look at a version which results in an array of smaller dimensions, not least because an attempt to reproduce in full the result of the above – a 1024-row-by-10-column (!) matrix – would make things a touch problematic.

Temporarily, then, and just for the purpose of aiding the deconstruction of this part of the formula, let’s assume that our range of possible values consisted of, not 10, but a mere 4 entries, i.e. that Values was defined, not as:

=$A$2:$A$11

but rather as:

=$A$2:$A$5

This being the case, we see that our Defined Name Arry1, which recall is:

=ROW(INDIRECT("1:"&ROWS(Values)))

would then resolve as:

ROW(INDIRECT("1:"&4))

i.e.:

{1;2;3;4}

and Arry2, which we defined as:

=ROW(INDIRECT("1:"&2^ROWS(Values)))

would resolve as:

ROW(INDIRECT("1:"&2^4))

which is:

ROW(INDIRECT("1:"&16))

i.e.:

{1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16}

Our construction, which is:

MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2)

is thus here:

MOD(INT(({1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16}-1)/2^(TRANSPOSE({1;2;3;4})-1)),2)

which becomes, resolving the TRANSPOSE and the subtraction of 1 from the resulting array:

MOD(INT(({1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16}-1)/2^({0,1,2,3})),2)

and then resolving 2 to the power of this array:

MOD(INT(({1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16}-1)/{1,2,4,8}),2)

and subtracting 1 from the first array:

MOD(INT(({0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15})/{1,2,4,8}),2)

We now perform the array of divisions, bearing in mind that, the two arrays here being orthogonal (the numerator being a 16-element single-column vector, the denominator a 4-element single-row vector), we know that the resulting array will comprise a 16-row-by-4-column array, the 64 entries in which being the result of dividing each of the 16 entries in the first array by each of the 4 entries in the second, the result being:

MOD(INT({0,0,0,0;1,0.5,0.25,0.125;2,1,0.5,0.25;3,1.5,0.75,0.375;4,2,1,0.5;5,2.5,1.25,0.625;6,3,1.5,0.75;7,3.5,1.75,0.875;8,4,2,1;9,4.5,2.25,1.125;10,5,2.5,1.25;11,5.5,2.75,1.375;12,6,3,1.5;13,6.5,3.25,1.625;14,7,3.5,1.75;15,7.5,3.75,1.875}),2)

Just to take a quick example as way of further clarification, the 5th row in this array, i.e. {4,2,1,0.5}, is the result of dividing the 5th member of the first array, i.e. 4, by each of 1, 2, 4 and 8 respectively.

We then take the integer portion only of each of these values, so that we now have:

MOD({0,0,0,0;1,0,0,0;2,1,0,0;3,1,0,0;4,2,1,0;5,2,1,0;6,3,1,0;7,3,1,0;8,4,2,1;9,4,2,1;10,5,2,1;11,5,2,1;12,6,3,1;13,6,3,1;14,7,3,1;15,7,3,1},2)

and then finally generate the results of this array modulo 2:

{0,0,0,0;1,0,0,0;0,1,0,0;1,1,0,0;0,0,1,0;1,0,1,0;0,1,1,0;1,1,1,0;0,0,0,1;1,0,0,1;0,1,0,1;1,1,0,1;0,0,1,1;1,0,1,1;0,1,1,1;1,1,1,1}

And if I just re-format this array so that it is clearer what is being represented:

0 0 0 01 0 0 00 1 0 01 1 0 00 0 1 01 0 1 00 1 1 01 1 1 00 0 0 11 0 0 10 1 0 11 1 0 10 0 1 11 0 1 10 1 1 11 1 1 1

then hopefully readers will be able to see that we have succeeded in creating an array which consists of all 16 permutations of a four-element set where the values within that set are either 0 or 1.

And the justification for having created such an array is that it gives us the means, once we arrange the appropriate matrix multiplication, to generate (and sum) all possible combinations from our entries in the Values range.

For example (and recall that we temporarily reduced our Values array to one of just four cells, i.e. A2:A5), the matrix product of the fourth row in this array and the entries in Values, i.e. of:

{1,1,0,0}

and:

{283.75;350.25;290.27;246.89}

which we would achieve in Excel by:

=MMULT({1,1,0,0},{283.75;350.25;290.27;246.89})

will give us the sum of the first and second entries (283.75 and 350.25) within our Values array.

Or, to take another example, the matrix product of the fifteenth row in this array and the entries in Values, i.e. of:

{0,1,1,1}

and:

{283.75;350.25;290.27;246.89}

which is, in Excel:

=MMULT({0,1,1,1},{283.75;350.25;290.27;246.89})

will give us the sum of the second, third and fourth entries (350.25, 290.27 and 246.89) within our Values array.

Since we have accounted for all permutations of 1s and 0s, we guarantee that all possible summations of values from our range are calculated, which of course is precisely what this challenge is all about.

Although we looked at the reduced case for a Values range comprising four cells, it can easily be verified that this construction is sufficiently dynamic as to work for ranges of other sizes too (within limits – see below). For example, if Values were instead a 5-cell range, e.g. A2:A6, then this construction:

MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2)

would this time resolve to the following array:

{0,0,0,0,0;1,0,0,0,0;0,1,0,0,0;1,1,0,0,0;0,0,1,0,0;1,0,1,0,0;0,1,1,0,0;1,1,1,0,0;0,0,0,1,0;1,0,0,1,0;0,1,0,1,0;1,1,0,1,0;0,0,1,1,0;1,0,1,1,0;0,1,1,1,0;1,1,1,1,0;0,0,0,0,1;1,0,0,0,1;0,1,0,0,1;1,1,0,0,1;0,0,1,0,1;1,0,1,0,1;0,1,1,0,1;1,1,1,0,1;0,0,0,1,1;1,0,0,1,1;0,1,0,1,1;1,1,0,1,1;0,0,1,1,1;1,0,1,1,1;0,1,1,1,1;1,1,1,1,1}

or, more helpful visually:

0 0 0 0 01 0 0 0 00 1 0 0 01 1 0 0 00 0 1 0 01 0 1 0 00 1 1 0 01 1 1 0 00 0 0 1 01 0 0 1 00 1 0 1 01 1 0 1 00 0 1 1 01 0 1 1 00 1 1 1 01 1 1 1 00 0 0 0 11 0 0 0 10 1 0 0 11 1 0 0 10 0 1 0 11 0 1 0 10 1 1 0 11 1 1 0 10 0 0 1 11 0 0 1 10 1 0 1 11 1 0 1 10 0 1 1 11 0 1 1 10 1 1 1 11 1 1 1 1

whose 32 rows readers may like to verify are precisely the 32 possible permutations of zeroes and ones for a 5-character string.

This construction for generating such arrays of permutations is extremely useful, albeit one which is restricted by the limitations imposed on certain functions (i.e. ROW, the range passed being limited to a maximum value equivalent to the number of rows in a worksheet, i.e .(post-2003) 2^20). Which explains my comment in the preamble, since, with this restriction, we are unfortunately not able to extend this construction so as to work for ranges comprising more than 20 values.

Anyway, returning to our deconstruction, we now see that, in full:

MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)

will return a 1024-element single-column array consisting of the sums of all possible permutations from our entries in Values (if readers weren’t already aware, 1024=2^10, 10 being the number of elements in our range), viz (I will not present all one thousand-plus entries for obvious reasons; just the first 50 entries should suffice to illustrate):

{0;283.75;350.25;634;290.27;574.02;640.52;924.27;246.89;530.64;597.14;880.89;537.16;820.91;887.41;1171.16;457.21;740.96;807.46;1091.21;747.48;1031.23;1097.73;1381.48;704.1;987.85;1054.35;1338.1;994.37;1278.12;1344.62;1628.37;123.69;407.44;473.94;757.69;413.96;697.71;764.21;1047.96;370.58;654.33;720.83;1004.58;660.85;944.6;1011.1;1294.85;580.9;864.65;...}

I have highlighted the one value in this array which is equal to our target value (a further two would be seen had I given the array in full, the 485th and 678th elements, to be precise).

We thus query this array of summations as to which, if any, is equal to the target value, such that:

MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1

which is now:

{0;283.75;350.25;634;290.27;574.02;640.52;924.27;246.89;530.64;597.14;880.89;537.16;820.91;887.41;1171.16;457.21;740.96;807.46;1091.21;747.48;1031.23;1097.73;1381.48;704.1;987.85;1054.35;1338.1;994.37;1278.12;1344.62;1628.37;123.69;407.44;473.94;757.69;413.96;697.71;764.21;1047.96;370.58;654.33;720.83;1004.58;660.85;944.6;1011.1;1294.85;580.9;864.65;...}=1054.35

gives:

{FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;...}

We then return the position of each of our Boolean TRUE returns within this array, so that:

SMALL(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1,Arry2),COLUMNS($A:A))

which is:

SMALL(IF({FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;TRUE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;...},{1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21;22;23;24;25;26;27;28;29;30;31;32;33;34;35;36;37;38;39;40;41;42;43;44;45;46;47;48;49;50;...}),1)

i.e.:

SMALL({FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;27;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;FALSE;...},1)

i.e. 27.

And so we know that the 27th of our 1024 summations which we formed is one which does indeed result in our desired total.

We now need to return to that array of 1024 permutations to find out which exact values were involved in that summation. Hence, we INDEX that array – which recall is a 1024-row-by-10-column matrix – with this value of 27 as the row parameter, such that:

INDEX(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),SMALL(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1,Arry2),COLUMNS($A:A)),)

which is:

INDEX({0,0,0,0,0,0,0,0,0,0;1,0,0,0,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0,0;1,1,0,0,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0,0;1,0,1,0,0,0,0,0,0,0;0,1,1,0,0,0,0,0,0,0;1,1,1,0,0,0,0,0,0,0;0,0,0,1,0,0,0,0,0,0;1,0,0,1,0,0,0,0,0,0;0,1,0,1,0,0,0,0,0,0;1,1,0,1,0,0,0,0,0,0;0,0,1,1,0,0,0,0,0,0;1,0,1,1,0,0,0,0,0,0;0,1,1,1,0,0,0,0,0,0;1,1,1,1,0,0,0,0,0,0;0,0,0,0,1,0,0,0,0,0;1,0,0,0,1,0,0,0,0,0;0,1,0,0,1,0,0,0,0,0;1,1,0,0,1,0,0,0,0,0;0,0,1,0,1,0,0,0,0,0;1,0,1,0,1,0,0,0,0,0;0,1,1,0,1,0,0,0,0,0;1,1,1,0,1,0,0,0,0,0;0,0,0,1,1,0,0,0,0,0;1,0,0,1,1,0,0,0,0,0;0,1,0,1,1,0,0,0,0,0;1,1,0,1,1,0,0,0,0,0;0,0,1,1,1,0,0,0,0,0;1,0,1,1,1,0,0,0,0,0;0,1,1,1,1,0,0,0,0,0;1,1,1,1,1,0,0,0,0,0;0,0,0,0,0,1,0,0,0,0;1,0,0,0,0,1,0,0,0,0;0,1,0,0,0,1,0,0,0,0;1,1,0,0,0,1,0,0,0,0;0,0,1,0,0,1,0,0,0,0;1,0,1,0,0,1,0,0,0,0;0,1,1,0,0,1,0,0,0,0;1,1,1,0,0,1,0,0,0,0;0,0,0,1,0,1,0,0,0,0;1,0,0,1,0,1,0,0,0,0;0,1,0,1,0,1,0,0,0,0;1,1,0,1,0,1,0,0,0,0;0,0,1,1,0,1,0,0,0,0;1,0,1,1,0,1,0,0,0,0;0,1,1,1,0,1,0,0,0,0;1,1,1,1,0,1,0,0,0,0;0,0,0,0,1,1,0,0,0,0;1,0,0,0,1,1,0,0,0,0;...},27,)

i.e.:

{0,1,0,1,1,0,0,0,0,0}

which array corresponds to taking the values from A3, A5 and A6 from our range, which do indeed sum to our target value.

The rest is relatively straightforward: we simply check whether the row in which the formula is placed corresponds to a non-zero value in this array, such that:

IF(INDEX(INDEX(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),SMALL(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Values)=$A$1,Arry2),COLUMNS($A:A)),),ROWS($1:4)),"X","")

which is here:

IF(INDEX({0,1,0,1,1,0,0,0,0,0},ROWS($1:4)),"X","")

i.e.:

IF(INDEX({0,1,0,1,1,0,0,0,0,0},4),"X","")

i.e.:

IF(1,"X","")

which is “X”, as required.

Finally, and thanks to Torstein for being the inspiration behind this addition, here is an amended version which has the added feature that the number of values to be considered is dynamic, and so can be defined by the user.

Here, then, we may enter this limiting value into e.g. L2, as below:

Which Numbers Add Up To Total (Multiple Solutions - Restricted Number of Values)

(You can download the workbook here.)

Here, this value in L2 represents the fact that we wish to only consider combinations of precisely 3 values from our 10 in A2:A11. Hence each of the 8 possible solutions that you can see does indeed consist of that number of values.

The required set-up this time is:

The array formula** in L1 is now:

=SUM(N(MMULT(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Arry1^0)=L2,MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),0),Values)=A1))

and that in B2:

=IF(COLUMNS($A:A)>$L$1,"",IF(INDEX(INDEX(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),SMALL(IF(MMULT(IF(MMULT(MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),Arry1^0)=$L$2,MOD(INT((Arry2-1)/2^(TRANSPOSE(Arry1)-1)),2),0),Values)=$A$1,Arry2),COLUMNS($A:A)),),ROWS($1:1)),"X",""))

Many thanks to Torstein and Oscar! Another post to follow shortly. Watch this space!

12 comments

  1. I posted this comment on get-digital-help.com but maybe you do not read it. Thays why I comment here too.

    Hi Oscar and XOR LX!

    I’m really impressed what you guys can do with excel formulas. I have been trying to figure out permutations for so long, but have not been able to make it.

    One question to the formulas: Is it possible to restrict solutions to those which have eg three numbers that adds to the total?

    Hope I make my self understood!

    Regards Torstein

  2. Torstein

    Welcome to the site and thanks for your kind words!

    It’s nice to know that some of the work I do here is of practical interest to some.

    As to your question: yes, this is possible. We could do it by first restricting the array of permutations of 1s and 0s such that each permutation contains precisely three 1s.

    I’m a touch busy at the moment, but if you bear with me then I’ll look into this and post a reply here when I’ve worked out the necessary amendments for this case.

    Regards

  3. Une remarque quand même: c’est plus rapide par VBA et le pc n’est pas ralenti par les formules matricielles, mais ici, c’est un superbe travail 🙂

    Patrick

  4. That’s great work you did, mate. Congrats!

    How many rows does your spreadsheet support? Is it limited to 10/11?

  5. @Leeroy

    Thanks! As I mention in the post, unfortunately this set-up has a limit of 20 values to be considered, though you may well find that calculation time beyond, say, 15 values, will be unfeasibly long.

    Regards

  6. Awesome solution. However, when I expand the values range up to A500 (my data would have sometimes reach that number of rows), the formula will just ave me #ref.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s