Sufficient implementation of subset sum for 45 min interview 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 &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;vector&gt;

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

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

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

int main()
{
    std::vector&lt;int&gt; set = {2, 3, 4};
    bool found = false;
    subset_sum(set.begin(), set.end(), 100, found);
    return (!found);
}
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.