# vector version of subset sum

Given a set of vectors $$V = \{v_1, v_2, \cdots, v_n\}, v_i \in \mathbb{Z}^2$$.

Given a query $$\vec{C} = (c_1, c_2), c_i \in \mathbb{Z}$$, how can one quickly verify whether if there exists a subset $$S\subseteq V$$, such that $$\sum_{v \in S}v == \vec{C}$$ ?

And I have a constraint on query $$\vec{C}$$ which only two forms are allowed $$(0, \sum_{v\in V} v[1])$$ or $$=(\sum_{v\in V} v[0], 0)$$

A brute force approach can be treating every dimension independently first and then somehow figure out a way to intersect both feasible regions.

• Your problem is at least as hard as subset sum (because the second coordinates could be all zero). Also you could encode your vectors $(x_1,x_2)$ as integers $x_1 + Mx_2$, with $M$ big enough. Then just solve as an ordinary subset sum problem. Now subset sum is NP-complete so finding a quick way may be nontrivial. Mar 23, 2021 at 2:42
• right, but I'm wondering if there is any better way to solve it so that it's not NP-complete. Mar 23, 2021 at 2:44
• Do you have any extra constraints e.g. on the values? Otherwise your problem is NP-complete because it contains SUBSET SUM as a special case (with second coordinates zero), and that is already NP-complete. Mar 23, 2021 at 2:46
• can you please put all the constraints in the question, instead of having people ekeing them out of you in Q&A fashion. Mar 23, 2021 at 5:30
• The new constraint looks interesting, but the problem still contains the one-dimensional subset sum. Mar 23, 2021 at 6:50