0
$\begingroup$

Is it possible to efficiently find the elements that make up a sum $S$ given a set of number sets which determine the sum elements? It seems like an NP-Complete problem, though I might miss something.

Given $N$ equal sized (different) number sets $E_n$ ($0<n<N$) we sum $N$ elements $e_i$ such that $S = \sum^{N}_{i=0} e_i$ with $e_i \in E_i$.

Now, can we find $\{e_0, ..., e_N\}$ that make up $S$ given $S$ and $\{E_0,...,E_N\}$?

It seems closely related to the subset sum problem, though, there is slightly more information available. Can we exploit that to efficiently break down $S$ into the summed elements?

$\endgroup$

1 Answer 1

1
$\begingroup$

I think there is direct reduction to subset sum.

Take all $E_i=\{0,a_i\}$ for "number" $a_i$ and this is subset sum.

Another approach is to take $E_i=\{0,a_i,\text{prohibitively large numbers}\}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.