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 ?
Computing every possible sum of integers taken from different sets
algorithms;sets