Sufficient implementation of subset sum for 45 min interview

Question

I am preparing for interviews, and have implemented a solution to this problem from Geeks for Geeks:

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

I don't fully have my head wrapped around the dynamic programming approach. If I provided the implementation below in an interview, and explained that there was a dynamic solution that could speed the solution up for a small N and S would my technique be acceptable? What would your thoughts be as the interviewer?

FWIW I now that there would be duplicate processing at the leafs of my recursive descent. If asked I would say the complexity of my algorithm would be: \$\Theta(2^N + 1 + (N + 2(N-1) + ...))=\Theta(2^N)\$

Given a set of size 2: (1, 2) The calls would be (1, 2) -> ((1), (2))
Given a set of size 3: (1, 2, 3) The calls would be

                                 (1, 2, 3)
                         (1)(2, 3)       (1, 2)(3)
                            (2)(3)       (1)(2)

Looking at this pattern I would state there are \$2^N + 1\$ calls.

---

#include <iostream>
#include <iterator>
#include <vector>

void subset_sum(
    std::vector<int>::iterator begin, std::vector<int>::iterator end,
    const std::size_t sum, bool &found)
{
    std::size_t local_sum = 0;
    for (auto it = begin; it != end && !found; ++it) {
        local_sum += (*it);
    }

    if (sum == local_sum) {
        found = true;
    } else if (local_sum < sum) {
        found = false;
        return;
    }

    for (auto it = begin + 1; it < end && !found; ++it) {
        if (!found) {
          subset_sum(begin, it, sum, found);
        }
        if (!found) {
          subset_sum(it, end, sum, found);
        }
    }
}

int main()
{
    std::vector<int> set = {2, 3, 4};
    bool found = false;
    subset_sum(set.begin(), set.end(), 100, found);
    return (!found);
}

Answer 1

Bug

I ran your program, replacing 100 with 6. This should have found the subset {2,4} as a solution but it didn't.

Your program searches for contiguous subsets which sum to the given value. I don't think that contiguousnous was specified by the problem in the link you provided.

Answer 2

I would expect you to be able to deduce the recursive relation that gives birth to the dynamic programming approach.

I'd also expect understanding the top-down v/s bottom-up approaches. Writing the bottom-up solution would get you bonus points, as it may be quite harder if you are nervous, but any almost-correct solution suffices.

Sadly or not, there is no other way to learn DP than solving problems. Do not give up easily as it's quite hard to really understand, but after a while it becomes natural and it becomes hard to understand why it took you so long to grasp something that now seems simple.

I recommend you to take a look to the "Competitive Programming 3" book by Steven Halim & Felix Halim (an older version is available for free).

Answer 3

The problem is NP complete, but trivially solvable in polynomial time with "sum" as a constant factor. If you don't say that it is NP complete (and if I care whether you know that kind of thing or not), you've lost.

Your solution only calculates sums of consecutive numbers. There are N^2 / 2 such sums. I have the impression that your code calculates up to 3^(N - 2) sums if a matching sum isn't found; for example if Sum = 1 and all items are equal to 2. That is hugely wasteful but doesn't manage to find all solutions. You should have checked a set of size 4 and 5 as well.

The usual method to find that there is a solution is creating a bitmap for the numbers 0 to Sum, then using it to find all numbers that are the sum of the first 0 elements of the set (just 0), the first 1 elements (0 and the 1st element), the first 2 elements (the elements in the bitmap, and those elements with set element 2 added), the first 3 elements (the elements in the bitmap, and the elements with element 3 added) and so on.

If Sum is large, say > 10^10, cleverness beyond a 45 minute test is needed.

Answer 4

Other answers have already mentioned that the recursive part of the algorithm only uses contiguous ranges in the search set to find the target value. I'll address style and some possible generalization here.

void subset_sum(
    std::vector<int>::iterator begin, std::vector<int>::iterator end,
    const std::size_t sum, bool &found)

The function subset_sum() is really a predicate since it returns true or false via the found argument depending on whether it finds a subset that sums to the target value. If you look at the C++ standard library, predicate functions generally have names like is_something() or has_something(), so I recommend that you change the name to has_subset_sum() to match that convention.

It looks odd that the function has return type void, but returns its true/false value via a reference parameter. It should really return a bool so that you can use it in expressions such as bool found = has_subset_sum(...);. This also eliminates the possibility of error using the function if you don't initialize the bool parameter to false before calling it.

The collection of numbers that you're searching has type int (a signed type), but the target value that you're searching for is std::size_t (an unsigned type). Pick one or the other and use it consistently throughout.

Finally, the first two arguments have type std::vector<int>::iterator, which restricts the use of this function to std::vector. If you make it a function template:

template <typename Titer>
bool has_subset_sum(Titer begin, Titer end, std::size_t sum);

you'll be able to use it with other container types (e.g. std::list, std::set, etc.) and other contained types (long, unsigned char, etc.). See below for an additional change that you should make if you decide to do this.

---

Within the function:

    std::size_t local_sum = 0;

As mentioned above for the sum parameter, this is unsigned, but it's used to accumulate signed values.

    for (auto it = begin; it != end && !found; ++it) {
        local_sum += (*it);
    }

The value of found doesn't change during the execution of the for loop, so you don't need to check it on every iteration.

Also, consider replacing the for-loop with std::accumulate:

#include <numeric>

std::size_t local_sum = std::accumulate(begin, end, 0);

---

    if (sum == local_sum) {
        found = true;
    } else if (local_sum < sum) {
        found = false;
        return;
    }

Shouldn't there be a return after the found = true; since you've just found the target value?

---

Others have already mentioned that the recursive part of the algorithm is flawed, but something else to note is that the expression begin + 1 in the for-loop constrains the iterator to being a RandomAccessIterator:

    for (auto it = begin + 1; it < end && !found; ++it) { ... }

A RandomAccessIterator offers the most capabilities of the standard iterators, and not all of the standard containers support it. If you're concerned about making your code usable with a wider range of container types (i.e. making it a function template as mentioned above), you should rewrite it to only use the increment operator which only means it needs to be an InputIterator which is the least capable of the standard iterators and is supported by all of the containers:

    auto it = begin;
    for (++it; it < end && !found; ++it) { ... }

---

In your main() function, you declare a std::vector<int> called set. I recommend renaming it to avoid confusion with the C++ standard library container, std::set; perhaps search_set.