Efficient reductions and algorithms for variants of Subset Sum

Pranjal Dutta, Mahesh Sreekumar Rajasree

Given $(a_1,\dots ,a_n,t)\in {\mathbb{Z}}_{\ge 0}^{n+1}$, the Subset Sum problem ($\mathsf{SSUM}$) is to decide whether there exists $S\subseteq [n]$ such that $\sum_{i \in S}…