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 
#include 
#include 

void subset_sum(
    std::vector::iterator begin, std::vector::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  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.

StackExchange Code Review Q#95818, answer score: 8