Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am studying the subset sum problem and come across a soluition for it:

#include<iostream>
#include<conio.h>

using namespace std;
int m,n,w[10],x[10]; //Global declaration of variables

void sum_subset(int s,int k,int r)
{
    int i;
    x[k]=1;
    if(s+w[k]==m)
    {
        for(i=1;i<=n;i++)
        {
            cout<<"x["<<i<<"]:"<<x[i]<<"\t";
        }
        cout<<"\n";
    }
    else
    {
        if((s+w[k]+w[k+1])<=m)
        {
            sum_subset(s+w[k],k+1,r-w[k]); //Recursive call
        }
    }
    if(((s+r-w[k])>=m)&&((s+w[k+1])<=m))
    {
        x[k]=0;
        sum_subset(s,k+1,r-w[k]);
    }
}

int main()
{
    //User input
    cout<<"Enter the no. of values :";
    cin>>n;
    cout<<"Enter the sum : ";
    cin>>m;
    cout<<"Enter the values :";
    int i;
    for(i=1;i<=n;i++)
    {
        cin>>w[i];
    }

    int r;
    r=0;
    for(i=1;i<=n;i++)
    {
        r+=w[i];
    }
    sum_subset(0,1,r); //call the function to solve the sum of subsets problem
    getch();
    return 0;
}

But I am wondering if we can solve this problem without recursion - is there a way to do that?

share|improve this question
 
You would need to break(or decompose) your function. Try it out. –  Maxood Nov 30 '13 at 22:19
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.