# Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

Given an integer bound $$W$$ and a collection of $$n$$ items, each with a positive integer weight $$w_i$$, find the subset $$S$$ of the items that maximizes $$\sum_{i \in S} w_i$$ while keeping this sum at most $$W$$. Or the decision version: Is there a subset obeying the at-most-$$W$$ rule with weight at least some number $$k$$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

Given a set of $$n$$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $$k$$)?

E.g., my textbook (Kleinberg and Tardos) as well as this have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

1. Do quick reductions exists between the two?
2. Why are these given the same name in the first place?
• Reduce the second to the first by taking $k=W$. The other direction is direct (verify first that $k \le W$). – Yuval Filmus Feb 18 '20 at 15:55
• @YuvalFilmus Thanks for the response! I understand now how to reduce the second to the first. But as for reducing the first to the second: It seems like you would run into trouble since you only want to know if there is a subset with weight at least some number $k$. Wouldn't checking all numbers from $k$ to $W$ using the second be exponential because it depends on the magnitude of the numbers? – kanso37 Feb 18 '20 at 23:13
• Right. Let’s assume $W-k=2^t$. Add weights $1,2,4,\dots,2^{t-1}$, and ask for a target of $W$. Perhaps a similar approach can be used in general. – Yuval Filmus Feb 18 '20 at 23:17
• What a clever technique! Thanks. – kanso37 Feb 19 '20 at 0:00

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $$W = k$$. There is a subset of sum at least $$k$$ and at most $$W$$ iff there is a subset of sum exactly $$k$$.
• The total weight of the new items is $$W-k$$.
• Every weight between $$0$$ and $$W-k$$ can be represented as a sum of a subset of the new items.
Having added this collection, we ask whether there is a subset summing to exactly $$W$$. It is not hard to check that there is a subset of the original collection whose sum is between $$k$$ and $$W-k$$ if there is a subset of the enlarged collection summing to $$W$$ exactly.
How do we add these items? The simplest case is when $$W - k = 2^t$$, in which case we can simply add $$1,2,4,\ldots,2^{t-1}$$. More generally, suppose $$2^t \leq W-k < 2^{t+1}$$, and let $$W-k = 2^t + C$$. We then add $$1,2,4,\ldots,2^{t-1},C$$.