find the numbers that their sum equals to another number

[ayman daraghmah]

I've a set of numbers , and another number , I want to write a program to find which numbers from set their sum equals the other number .

[Joerg Meier]

Post by ayman daraghmah
I've a set of numbers , and another number , I want to write a program to find which numbers from set their sum equals the other number .

Ok.

[Pascal J. Bourguignon]

I've a set of numbers , and another number , I want to write a program
to find which numbers from set their sum equals the other number .

Good. Now you need an algorithm.


One way to find an algorithm is to extract it from your brain. Just
solve the problem yourself, taking note of how you mentally proceed.

How would you do it?

Take an example, write the numbers: 1 11 19 17 7 13 2
in black each on a little piece of paper.

Write the number 31 in red on another little piece of paper.

Then solve yourself this example problem, noting how you do it.



Another way to find an algorithm is to write mathematical equations and
mathematical proofs about the problem. This works well, because
algorithms and mathematical proofs are equivalent (even of there's often
little intersection between the set of useful algorithm and the set of
mathematically interesting theorem, they're basically the same, and it's
useful to have proofs of algorithms).

So you could write that:

Let S = { Ni | Ni ∈ ℂ }
Let T ∈ ℂ
Let Q(S)(T,R) ≡ R⊂S ∧ T = ΣR

So you want to find whether ∃R, Q(S)(T,R)
and if that's the case, you may want to find all the subsets R of S such
as Q(S)(T,R).

For this, you only have to solve the equation:

R⊂S ∧ T = ΣR

There are two parts: R⊂S and T = ΣR (no punt intended)
So you now have to find all subsets R of S on one hand,
and on the other hand, compute ΣR and compare it with T.


To find all subsets R of S, you can use the following properties:

∅⊂S
V⊂S ⇒ (∀n, n∈S ⇒ V∪{n}⊂S)

This comes directly from the definition of subset:

V⊂S ⇔ (∀n, n∈V ⇒ n∈S)
V⊂S ⇔ (∀n, n∈V ⇒ n∈S ⇒ {n}⊂S ⇒ V∪{n}⊂S)


So, the set of all subsets of S, P(S)
can be defined as the set such as:
If S=∅
then P(S) = {∅}
else P(S) = {∅} ∪ map( (λV.{e}∪V), P(S∖{e}) ), with e∈S

which translates directly to the algorithm to compute all the subsets of
S, as long as you have a way to find one element e of S.


So now you have all the subsets of S, you can sum each of them and
compare the sums to T and collect the subsets for which it's the same.