Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## Combinations of numbers that add up to a total.

I looked around for a solution but could not find one. I am trying to find combinations of numbers that can add up to a total. The numbers available and the total are different each time.

For example, I have an array that contains the following numbers:
[16,12,8,6,4,2]

I want to find the combinations that add up to 140, like this:
8x16,1x12
8x16,1x8,1x4
11x12,1x8

Notice I do not do:
8x16,2x6
8x16,3x4

This is because as a rule, only the first number can be used in multiple of more than one. All other number pairs can only be a 1x.

Output string could be formatted like this in a single string containing all combinations:
8x16,1x12|8x16,1x8,1x4|11x12,1x8

• Looks like homework to me...

• Its not homework, but thanks for looking.

I'm stuck on this problem and am looking for an elegant way to do it. I gave a simple starting array, but it could be far more complex, such as [64, 48, 40, 36, 32, 28, 24, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2], which would produce a larger number of combinations. Even larger arrays would be expected when testing with larger totals, so something fast and efficient is needed.

• So what do you use this for then?

• If I understand you correctly only the first number pair is actually a pair (i.e. to items from the array) - all other are just one item from the array?
Or are each pair always only one from the array and the multiple can be arbitrary?

• Not to ask a dumb question, but what is the point in displaying the 1x values?

That is, why

8x16,1x12
8x16,1x8,1x4
11x12,1x8

8x16,12
8x16,8,4
11x12,8

And why is it listed in that order instead of larger number first?

16x8,12
16x8,8,4
12x11,8

It is the kind of requirements you put on it that make it feel like homework. Doesn't feel like a real world problem.

Oh...and where did 11x12 come from? There's no 11 in your original array.

Anyway, there's really no answer for this except recursion. Probably could be done without it, but so much easier to conceive of using recursion.

• This is being used for an imposition model (how to layout things on a bigger area).

Your right, there is no point in displaying the 1x notation, other than for readability. It could very well be:
8x16,8,4
11x12,8
4x32,12

Regardless, the final output contains all the possible combinations in a single string separated by a delimiter, for example:
8x16,8,4|11x12,8|4x32,12|etc.

8 x 16 + 8 + 4 = 140
11 x 12 + 8 = 140
4 x 32 + 12 = 140

First number is arbitrary, but the second is always from the array. Only the first number can be used more than once (8x16, all others are 1x).

Hope that helps clarify it.

• Okay, almost have it. But one more thing:

For example, I have an array that contains the following numbers:
[16,12,8,6,4,2]

I want to find the combinations that add up to 140, like this:
8x16,1x12
8x16,1x8,1x4
11x12,1x8
Ummm... once again, you do *NOT* have 11 in your array. So will ignore that one.

But...

*ARE* you allowed to use the same number twice???
8x16,1x8,1x4
??? That seems inconsistent with your other rules.

And your list there is wrong, as I read it. You are missing possibilities.

My result:
Code:
```[16,12,8,6,4,2]

16x8,1x12|16x8,1x8,1x4|16x8,1x6,1x4,1x2|16x6,1x16,1x12,1x8,1x6,1x2|12x8,1x16,1x12,1x8,1x6,1x2```
Again, that assumes I can re-use a number in a "1x" when it has already been used in the first product.

• Here, rather than waiting for you:
Code:
```<html>

function targetFromArray( arr, target )
{

// sort descending, just to be safe
arr = arr.sort( function(n1,n2) { return n2-n1; } );

// first, find factors:
for ( var i = 0; i < arr.length; ++i )
{
var n1 = arr[i];
var ar2 = arr.concat([]); // clone the array
ar2.splice(i,1); // remove n1 from it

for ( var j = i+1; j < arr.length; ++j )
{
var n2 = arr[j];
var ar3 = ar2.concat([]); // clone the array
// then remove n2 from it
for ( var n = 0; n < ar3.length; ++n )
{
if ( ar3[n] == n2 )
{
ar3.splice( n, 1 );
break;
}
}
var product = n1 * n2;

var list = n1 + "x" + n2;
if ( product == target )
{
} else if ( product < target ) {
sumFromArray( list, ar3, target - product );
}
}
}
}

function sumFromArray( list, arx, target )
{
for ( var i = 0; i < arx.length; ++i )
{
var n = arx[i];
var nlist = list + ",1x" + n;
if ( n == target )
{
} else if ( n < target ) {
var ary = arx.concat([]);
ary.splice( 0, i+1 );
if ( ary.length > 0 ) sumFromArray( nlist, ary, target - n );
}
}
}

var test = [8,2,16,4,12,6];

function testit() { document.getElementById("result").innerHTML = targetFromArray( test, 140 ); }

</script>
<body>
<input type="button" value="try it" onclick="testit()"/>
<div id="result"></div>

</body>
</html>```
That code does *NOT* use "1xN" where "N" is one of the number in the first product.

So for
Code:
```test = [8,2,16,4,12,6];
result is 16x8,1x12|16x8,1x6,1x4,1x2```
If you want to have "1xN" where "N" is already in the first product, make one tiny change:
Code:
```            } else if ( product < target ) {
sumFromArray( list, ar3, target - product );
}```
to
Code:
```            } else if ( product < target ) {
sumFromArray( list, arr, target - product );
}```
Then for
Code:
```test = [8,2,16,4,12,6];
result is 16x8,1x12|16x8,1x8,1x4|16x8,1x6,1x4,1x2|16x6,1x16,1x12,1x8,1x6,1x2|12x8,1x16,1x12,1x8,1x6,1x2```
Happy?

• Wow, that looks complicated How about:
Code:
```//possibleParts(numbers:array,target:number)
var possibleParts = (function(){
var r;
var a = function(numbers,target,partial){
var i, s;
for(i=0,s=0;i<partial.length;s+=partial[i++]);
if(s > target){return};
partial.s = s;
(s == target || 0 == (target-s)%partial[0]) && r.push(partial);
for (i = 0; i < numbers.length; i++){
a(numbers.slice(i+1),target,partial.concat(numbers[i]));
};
};
var b = function(x,target){
for(var i = 0; i < x.length; i++){
for(var j = 0; j < x[i].length; j++){
x[i][j] = j == 0 && x[i].s < target
? ((target-x[i].s+x[i][0])/x[i][0]) + 'x' + x[i][0]
: x[i][j] = '1x' + x[i][j];
};
x[i] = x[i].join(',');
};
x = x.join('|');
return x
};
return function(numbers,target){
r = [];
a(numbers,target,[]);
return b(r,target)
}
})();```

• Test:
possibleParts([16,12,8,6,4,2],140)
Result:
8x16,1x12|7x16,1x12,1x8,1x6,1x2|8x16,1x8,1x4|8x16,1x6,1x4,1x2|11x12,1x8|10x12,1x8,1x6,1x4,1x2|11x12, 1x6,1x2|16x8,1x6,1x4,1x2|17x8,1x4|23x6,1x2|35x4|70x2

• Doesn't seem to work.

Calling possibleParts([16,12,8,6,4,2],140)

Produced this result:
8x16,1x12|7x16,1x12,1x8,1x6,1x2|8x16,1x8,1x4|8x16,1x6,1x4,1x2|11x12,1x8|10x12,1x8,1x6,1x4,1x2|11x12, 1x6,1x2|16x8,1x6,1x4,1x2|17x8,1x4|23x6,1x2|35x4|70x2

??? It seems to ignore the array of numbers.

EDIT: So we agree. And it doesn't fulfill the conditions he asked for, at all.

• I think it does exactly what he asks for ;-)
(Took me a while to understand what was asked for:
in each result the first item can be multiplied several times)

• <shrug> I guess we will find out, if he ever comes back.

I do note that adding that condition to your code would be easy, so not a big deal.

•
Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•