CODEWITHSUNDEEP
c++algorithmrecursion
sparta93
sparta93

Reputation: 3854

Modifying a subset sums recursive algorithm

Currently, I have the following recursive algorithm to solve the subset sum problem. It checks whether any combination of elements in a given vector sum up to a target number. For example, If A= {1,2,3,4,5} and target = 8, then it should return true as 1+2+5=8. Currently it works perfectly. However I want to make one change to it. I assign values to one of the function parameters in my main and I'm trying to not do that. All I want to do is call the function in my main. Not sure how I would attempt doing that. Any help is appreciated!!

bool subsetsum_imp(vector<int> & vec, int n, int sum) {

    if (sum == 0) {
        return true;
    }

    if (n == 0 && sum != 0) {
        return false;
    }

    if (vec[n-1] > sum)     
        return subsetsum_imp(vec, n-1, sum); 

    return subsetsum_imp(vec, n-1, sum) || subsetsum_imp(vec, n-1, sum-vec[n-1]);
}

The value n is assigned in my main as follows or else the algorithm doesn't work, How can I incorporate this into my function somehow so I don't have to write it in my main?

int n = sizeof(vec)/sizeof(vec[0]);

Upvotes: 0

Views: 144

Answers (1)

dohashi
dohashi

Reputation: 1841

Use a wrapper function that calls the recursive function. Something like:

bool subsetsum( vector<int> & vec, int sum )
{
    return subsetsum_imp( vec, vec.size(), sum );
}

Upvotes: 2

Related Questions