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);}
Sufficient implementation of subset sum for 45 min interview
c++;algorithm;c++11;interview questions;complexity
BugI 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.