1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\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$ Oct 29, 2020 at 11:06

1 Answer 1

1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Could you explain the whys? Which is what my original question was. $\endgroup$ Oct 29, 2020 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$ Oct 29, 2020 at 13:02
  • $\begingroup$ Are you familiar with dynamic programming? $\endgroup$ Oct 29, 2020 at 15:01
  • $\begingroup$ I am, but how does "memorisation" help when all possible sums are unique? $\endgroup$ Oct 29, 2020 at 15:17
  • 1
    $\begingroup$ I think you don't have a very good conceptual understanding of dynamic programming. This is a textbook example of dynamic programming. I suggest writing down the dynamic programming algorithm and analyzing its running time. $\endgroup$ Oct 29, 2020 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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