In class, we discussed two question types: 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 the first problem(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. I am not sure if we could use dynamic programming in this case also?

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:

My second confusion is that why cannot we use the second approach (using a linked list to store all the possible sums) to solve the unconstrained subset sum problem?

Question 3:

Finally, my final question is that, in this case(i.e. for the constrained subset sum), 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 unique subsets and so we will never share subproblems?

  • $\begingroup$ You can do a lot better than $2^n$. The classic meet-in-the-middle algorithm runs in time roughly $2^{n/2}$. $\endgroup$ – Yuval Filmus Oct 29 '20 at 11:06

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).

  • $\begingroup$ Could you explain the whys? Which is what my original question was. $\endgroup$ – user123215321631443 Oct 29 '20 at 13:00
  • $\begingroup$ I understand that the number of potential sums will be different in each case, but when we implement it, woudln't we need to explore all the different sums anyway? $\endgroup$ – user123215321631443 Oct 29 '20 at 13:02
  • $\begingroup$ Are you familiar with dynamic programming? $\endgroup$ – Yuval Filmus Oct 29 '20 at 15:01
  • $\begingroup$ I am, but how does "memorisation" help when all possible sums are unique? $\endgroup$ – user123215321631443 Oct 29 '20 at 15:17
  • $\begingroup$ Why do you expect them to be unique? For example, if $x_1 = \cdots = x_n = 1$, are all sums unique? $\endgroup$ – Yuval Filmus Oct 29 '20 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.