Computing every possible sum of integers taken from different sets I'm trying to proove $NP$-membership for a problem from the following certificate.
I have $n$ sets of integers :
$$(S_i)_{i \in \{1,\dots,n\}}$$
Each set has a number $m_i$ of integers.
I make "combination" from those sets by taking at most one element in each set.
A "combination" has between $0$ and $n$ elements (assuming sets are not empty).
A "combination" has a value : the sum of its elements.
I have to compute the sum of every possible "combination" values,
and look if it is greater than a given value.
An analytical formula would be nice, but I'm not sure it exists.
Otherwise, do you think this sum is easily computable ?
$C_0=\{0\}$, $C_{k} = C_{k-1} \cup \{ x+y \mid x\in C_{k-1}, y\in S_k \}$.