On variations of the subset sum problem

AbstractIn the well-knownSubset Sum Problem, we are given positive integersa1, ..., an andt and are to determine if some subset of theai sums tot. We investigate the boundary between easy and hard variations of this problem. In particular, we consider the cases where the sequencea1, ..., an is an arithmetic progression, a chain or superincreasing and where theai may be replicated. We also consider related problems