Subset sum whose set contains only positive integers

Question

I was trying to write a dynamic programming algorithm using a bottom up approach that solves the subset sum problem's version where the solution can be either an empty set and the initial set can only contain positive integers.

The following is my implementation, but I am not sure it is correct for all cases.

def _get_subset_sum_matrix(subset, s):
    m = [[0 for _ in range(s + 1)] for _ in range(len(subset) + 1)]

    for i in range(1, s + 1):
        m[0][i] = 0

    for j in range(0, len(subset) + 1):
        m[j][0] = 1

    return m


def subset_sum(subset, s):
    m = _get_subset_sum_matrix(subset, s)

    for i in range(1, len(subset) + 1):

        for j in range(1, s + 1):

            if subset[i - 1] == j:
                m[i][j] = 1
            else:
                # We can include the current element,
                # because it is less than the current number j.
                if subset[i - 1] <= j:
                    m[i][j] = max(m[i - 1][j], m[i - 1][j - subset[i - 1]])
                else:
                    m[i][j] = m[i - 1][j]

    return m[-1][-1]

You can imagine the idea of my algorithm as follows.

I have the numbers of the set in the vertical axis on the left, where the first element is actually the empty set. These numbers are not considered as only numbers, but, as I go down from the empty set (the first element), I start considering greater sets, that include all previous elements plus the current one.

Example, suppose I have the set S = {1, 2, 3}. I first consider the empty set, then the union of the empty set and {1}, then the union of {1} and {2}, and finally the union of {1, 2} and {3}.

In the horizontal axis you can imagine I have an increasing sequence of numbers up to the number we want to obtain (by summing the numbers of a certain subset of S). Example, suppose we want to obtain 4, then the increasing sequence would be 0, 1, 2, 3, 4.

So, I first start considering I want to obtain the number 0, and then 1, 2, etc, as it is usually done in a dynamic programming algorithm using a bottom-up approach.

Apart from the setup of the matrix, my algorithm assigns 1 to m[i][j], for some i = 0, 1, ..., N, where N is the size of the set S, and for some j = 0, 1, ... , M, where M is the number we want to obtain, when either the current number in the subset, that is S[i - 1], is equal to the number we want to obtain M_j, or when the previous solution to the subproblem, where the number we want to obtain is M_j - S[i - j], was 1.

That might seem a confusing explanation, and I think the code is self-explanatory.

Is my algorithm correct for all instances of the problem?

Is there a way I can improve it?

Answer 1

First of all I, for one, do not think your code is self-explanatory. I've read it quite a few times, and if I do understand the code you've written, but I still fail to properly understand your logic. In other words, your code would benefit greatly from some test cases, with proper explanations around them. Even a link to which algorithm you are attempting to implement would be better.

So here are some other stylistic and code review items:

• Spacing is good, but could have more comments – I like both your vertical and horizontal spacing. This renders the code easy, but I do miss some comments here and there to indicate more of the algorithmic meaning of your code.
• Somewhat good naming – You are not very fond of long names, I gather, and some of the like the loop indices, i, j, I don't mind. And I kind of understand the m for matrix, but the s is just a little random. I would consider at least explaining some of the latter ones even if you keep them short for brevity of the code.

• Function naming is somewhat unclear – I would rather use build_subset_sum_matrix() instead of get, as you don't simply fetch a value, you do build an entirely new matrix.

  The same applies for the subset_sum, it is not quite clear what this function actually does. It does something related to subsets and sum, but what?

• Don't understand your range's – Using range(1, s + 1) seems kind of strange, and I think I would have used range(s) instead. Similarily later down you do range(1, len(subset) + 1), when you could have done range(len(subset)). This would of course change that instead of i and i - 1 you do i - 1 and i, or similar.

• Why reset 0 to 0? – Within your first function you first set all element to 0, and then you reset m[0][i] = 0. Why? (I would also consider switching around i and j to match the other function...)

  In fact you simplify the entire function to a list comprehension like the following:

  def build_subset_sum_matrix(subset, size):
      return [[0 if i > 0 else 1 for i in range(size + 1)] 
              for _ in range(len(subset) + 1)]
  

Most of these comments are minor issues, and some personal preferences, as the main issue you are trying to solve still alludes me somewhat. In other words, I'm not sure that your code actually does what you want it to do, and that it is the optimal solution.

Add testing

To accommodate this I would strongly suggest to add multiple tests to your code to verify correctness. Try to vary these tests as much as possible to cover most edge cases, and use them to further explain your algorithm.

There are loads of variations, and I'll only suggest two of the more standard approaches. Namely that of the modules unittest and doctest.

The latter one allows stuff like the following variant of the modified build subset sum matrix:

    def build_subset_sum_matrix(subset, size):
        """Initialize a matrix with 1's and 0's.

        >>> build_subset_sum_matrix([1, 4, 10], 4)
        [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]
        """
        return [[0 if i > 0 else 1 for i in range(size + 1)] for _ in range(len(subset) + 1)]

This could be run always by doing an import doctest, and then a doctest.testmod() somewhere in your file. If the test runs expectedly, you don't see anything, but if the wrong result is generated you get some error messages. See more information in the links given above.