Given a collection of m-bit binary strings s1 , s2 , . . . , sn , and a nonnegative integer K, the String Sum decision problem is to decide if there are K strings si1 , si2 , . . . , siK from the collection such thatsi1 + si2 + · · · + siK = 1,where the addition is bitwise Boolean-algebra addition (e. g. 1001 + 1010 = 1011), and 1 is the m-bit binary string consisting of all ones.
Prove that String Sum is an NP-complete decision problem.