Koen wrote:

> Hi,

>

> I am looking for an algorithm that figures out which numbers from a

> given set add up to another number. I am sure this has been done

> before, but I have no idea how such a calculation is called, which

> kind of limits my further searching.
Are you talking addition or multiplication or both?

The above paragraph talks about addition, but the solutions show

multiplication.

>

> An example. The set contains the numbers 1-2-3-4-5. Now the algorithm

> should calculate all possible combinations of these numbers that add

> up to 10. Each number can be used more than one time or not at all.
Again, you state addition, but the example shows multiplication.

What is exact definition of the problem?

>

> possible solutions are:

>

> 10 x 1

> 5 x 2

> 3 x 2 + 4

> 1 + 4 + 5

> 2 + 3 + 5

> 1 + 2 + 3 + 4

>

> etc.
Let us see, the first solution is invalid according to the given rules.

"10 x 1" is not a solution because the number "10" is not a member of

the set [1,2,3,4,5].

According to your problem definition, the first three solutions:

10 x 1

5 x 2

3 x 2 + 4

are all invalid solutions since they involve multiplication.

>

>

> In this case it's pretty easy to do it on paper, but when the numbers

> become larger (>1000) it would be nice to have a program to do this.
As I've been thinking about this problem, it is not easy.

The given solution set does not match the problem definition.

The number of solutions involving mulitiplication is not a finitie

set, given the rule that any number may be used more than once and

the rule of multiplication by 1.

Addition, on the other hand, is a finite set, as long a zero is not

within the set. The rule of addition with zero provides an infinite

quantity of terms for a solution.

> Any suggestions how to do this and/or where to start looking ?
Yes, get your problem definition correct before proceeding.

Start looking at:

combinatorics

recursion

linked list

stack

Identity Theorum for Multiplication

Identity Theorum for Addition

Programming loop constructs.

Greatest Common Factor (GCF)

Lowest Common Denominator (LCD)

logarithms (sp?)

Series expansion

If this is homework, slap your instructor and say "bad assignment"

then ramble off the Identity Theorums and say this is a never

ending waste of computer cycles (the same as an infinite loop).

>

>

> thanks,

>

> - Koen.
I would first start out with either multiplication or addition and

get them working. The multiplication with addition adds more

complexity to the function (as well as combinations).

Since "Each number can be used more than one time",

how does one know when to stop?

For example,

5 x 2

5 x 2 x 1

5 x 2 x 1 x 1

5 x 2 x 1 x 1 x 1 ...

--

Thomas Matthews

C Faq:

http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:

http://www.raos.demon.uk/acllc-c++/faq.html