Confusion about dynamic programming on unconstrained subset sum vs constrained subset sum

Question

In class, we discussed two problems: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.

Question 1: Given an unconstrained set of numbers, find whether or not a certain subset of them adds up to a target value.

Question 2: Given a constrained set of numbers, find whether or not a certain subset of them adds up to a target value.

Now in answer to these questions, our professor mentioned that in the former case, there is no way to do better than $2^{n}$ since we would need to check all possible combinations of the $n$ numbers. But in the second case, we can do better since if we know our numbers are in the range of $[0,n]$, our sums can only be in range $[0, n^{2}]$, so our running time may be polynomial and not exponential. I have understood up until this point, but when discussing the specific implementation of the two programs is where I am confused.

So, for unconstrained subset-sum, the idea is that we do an implicit traversal of a tree. Where for each number in the set we say, use this or no don't use this. So we get $2^{n}$ possible combinations.

But in the other case, the approach used in class was we used a linked list to store all the possible sums that could be computed by a certain subset of the numbers, and then we took another number from the set, and added it to all the values in the linked list to generate all possible sums that could be formed using this number. If the number is already in the list, we don't bother to add it.

Question 1:

What I fail to understand is that, how come this time around the running time is polynomial, when really we are still trying to generate all possible sums like we did the last time? After all we are still trying to generate all possible sums right?

Question 2:

I saw that we could use dynamic programming. I am wondering how we can use DP, because the way I am looking at it, each time we are generating a unique subset and so we will never share subproblems?

Question 3:

Why cannot we use the second approach (using a linked list to store all possible sums) to solve the unconstrained subset sum problem?

Answer 1

If you have $n$ non-negative integers $x_1,\ldots,x_n$ in the range $0,\ldots,T$, then their susbets can sum up only to integers in the range $0,\ldots,nT$. This allows us to solve SUBSET-SUM efficiently in the constrained case. The idea is to use dynamic programming: for $m = 0,\ldots,n$, we determine which of the $nT+1$ potential sums are achieved by subsets of $x_1,\ldots,x_m$.

When $T$ is small, say polynomial in $n$, then this leads to a polynomial time algorithm. This is the constrained case. When $T$ is arbitrary, the corresponding algorithm is not efficient. This is the unconstrained case. The difference between the two cases is the number of potential sums – in the constrained case there are only polynomially many potential sums, in the unconstrained case there could be a lot more. In other words, you can use the dynamic programming algorithm in both cases, but the algorithm will only be efficient in the constrained case.

Let me also mention that the $O^*(2^n)$ algorithm in the unconstrained case can be dramatically improved upon using meet-in-the-middle, to $O^*(2^{n/2})$. A naive implementation of meet-in-the-middle uses a lot of memory, $\Theta^*(2^{n/2})$, but this can be improved to $O^*(2^{n/4})$ (the classic Schroeppel-Shamir algorithm).