# Subset sum with multiple lists

Given n lists of m elements each we need to obtain sum S by selecting one element from each list. Is corresponding decision problem NP-complete? Are there papers about it?

Given a subset sum instance with item set $A = \{a_1,\ldots,a_n\}$ and target value $B$, we set $S = B$, $m = 2$, and create one list for each $a \in A$ with the two values $(a, 0)$. Basically, for each $a \in A$, you then have the choice to either take it (if you take $a$) or to not select it (if you take $0$). The requirement to "select one element from each list" is then translated into "you are allowed to pick each element at most once".