On 12/21/05, adak <[EMAIL PROTECTED]> wrote:
>
> Why can't the sum of the subsets be an odd number? Makes no difference,
> it's just a sum.imo
Let's suppose you have the solution of the problem; you have two subsets
s' and s'' of a set of integers S such that the sum of all the elements of s'
is equal to the sum of all the elements of s''. Obviously,
SUM(s')+SUM(s'') = S
can't be odd, because its the sum of two equal numbers !!! :)
> When I think of "an exhaustive search algorithm", for a problem, I
> think it needs to generate ALL the subsets, until it either finds the
> answer I'm seeking, or all the subsets have been examined, and there is
> no answer matching my request.
going this way, complexity is something like 2^|B|
(where |x| means cardinality(x) :)
let's suppose you create an array of boolean B with a number of cells
equal to the number of elements in the set S.
S[] array of integer;
B[] array of boolean;
s', s'' integer;
s'=0;s''=0;
for each permutation of B
for (i=0 .. |B|)
if (B[i] == true) S'++;
else S''++;
end'
if (s' == s'') return B;
s'=0;
s''=0;
end;
Given that we hopefully have to work in a world where
|B| <<< 2^|B|
(<<< means: "very, very, very lower than" :)
complexity of the problem is 2^|B|.
Am I wrong somewhere ?
bye ! :)
Mattia Merzi.
