Subset Sum

Karp showed that two problems were equally hard by giving rules for translating problems of one form into the other form and doing the same with their solutions. For example, subset sum problems: Given a set of integers, and a target number S, is there a subset whose sum is S? Given the set 7, 3, 4, 5, 8 and the target S = 10 the answer is “Yes, (7, 3).” For S = 6 the answer is “No”.

To translate a subset sum problem into the knapsack problem that Ness and I attacked, each number is translated into an item with that number as both its weight and usefulness and the target S is used for both the total weight and usefulness. If there is a set of items that satisfies the knapsack problem’s challenge (total usefulness at least U and weight not exceeding W) then, and only then, the number for their usefulness satisfies the subset sum’s challenge because they must add up to precisely S lest their weight doesn’t exceed S.

It is also possible to translate any knapsack problem into a subset sum problem.