# What is the complexity class of this variant of Subset sum?

Let's represent Subset Sum problem with binary arrays instead of numbers. Example: given two-dimensional array

[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)


is there set of one-dimensional arrays, sum of which is equal to

[1, 0, 0, 1] (9)


In this problem sum of bits in each position can have carry-over. If carry-overs are forbidden (bit positions are independent) and we ask instead: are there arrays which sums to

[2, 0, 1]


then what complexity class such problems belong to? In what papers it was studied?

This is NP-hard. The associated decision problem is NP-complete.

There are various ways to prove that. For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard.

Your problem is an instance of multi-dimensional subset sum (or multi-dimensional knapsack), for which you can find algorithms and approximation algorithms in the literature.