OK, another maths question

[Taffy_is_a_Taff]

if I have a set of n numbers and these numbers could be added together in combinations of up to m (allowing for duplications) how would I find all the possible combinations?

So say n {1,2} and m were 2 then I could have combinations that came to: 1,2,3,4.

1 from 1
2 from 1+1 or 2
3 from 1+2
4 from 2+2

However, I need to be able to do this for potentially any set of n and up to any m.

anybody got relevant algorithms floating around?

cheers,

Taffy

P.S. :help:

[Papewaio]

Factorials. 2n!

[Uesugi Kenshin]

I was thinking he was talking about factorials, but for some reason it didn't seem quite the same....They seem to be a bit different, it looks to me like he wants a formula to come up with the set of all numbers that can be formed by adding a set of numbers together in different ways.

Factorials are multiplication, like 6! is 6x5x4x3x2x1 right?

I haven't done this in a while though, and haven't gotten to any algorithms yet so I could be wrong.

[Ironside]

n^m covers the additions of numbers (I think, more based on memory than actual calculation) but not the lower m combinations (AKA m=3, then it doesn't cover the numbers for m=2,1). So I'm guessing n^m would work.

Problem is that to cover all numbers you'll need n^m+n^(m-1) + ... + n^1. :inquisitive:

Should be a better way to combine that.

[Narayanese]

If I understand the problem correctly, the answer is all numbers from 1 to m*n, because if one sum is possible then the sum one smaller is possible too because you can always chose a number in a term one smaller, and the largest sum possible is having all the m terms equal to n.

[Rodion Romanovich]

IIRC it's an NP complete problem. You have to test all possibilities to find the solution. Some clever tricks can make it slightly faster, but it's basically about testing all combinations.

[Ironside]

My basic formula was a bit too number counting, it includes all combinations, even though 1+1+2, 1+2+1, 2+1+1 could be treated as the same.