Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

Changlin Wan, Zhongzhi Shi

The subset sum problem (SSP) can be briefly stated as: given a target integer $E$ and a set $A$ containing $n$ positive integer $a_j$, find a subset of $A$ summing to $E$. The \tex…