How does this solution of the subset sum problem work?

Question

this is a solution for the subset sum problem. It uses backtracking. I have been thinking about it for more than 2 hours now and i just cannot understand it.

edit:I have added some comments to the code based on what i have understood. Please correct me if i am wrong.

#include <iostream>

int n, d, w[10], x[10], count=0;

void subset(int cs, int k, int r)//i dont understand the purpose of cs or of the array x[] 
{
    int i;
    x[k] = 1;

    if(cs + w[k] == d)      //if the first element is equivalent to the sum that is required 
    {
        std::cout<< "\n\nSolution " << ++count << " is:"; 
        for(i=0; i<=k; i++)  // so if the subset criteria are met then the array is printed.
        if(x[i] == 1) 
            std::cout << w[i] << " ";
    }
    else if(cs + w[k] + w[k+1] <= d) //if the node is promising then go to the next node and              
        subset(cs + w[k], k+1, r - w[k]); //check if subset criteria are met

    if(cs + w[k+1] <= d && cs + r - w[k] >= d) //else backtrack
    {
        x[k] = 0;
        subset(cs, k+1, r-w[k]);
    }
}

int main()
{
    int sum=0, i;

    std::cout << "enter n\n";
    std::cin >> n;

    std::cout < <"enter " << n << " elements\n";
    for(i=0; i<n; i++)
        std::cin >> w[i];

    for(i=0; i<n; i++)
        sum += w[i];

    std::cout << "enter value of sum\n";
    std::cin >> d;

    if(sum < d)
        std::cout<<"INVALID SOLUTION\n";
    else
        subset(0,0,sum);

}

Note: This is a working solution. It works when compiled with g++. I am sorry if this seems too obnoxious but i just did not understand much from the code and hence i cannot give much of an explanation.

Answer 1

cs is the current sum and x[] is an array that has 1 set for those elements that belong to the solution branch that is currently being explored.

Answer 2

cs is the sum of values of the weights chosen so far, while r is the remainder of the summed values of the weights yet to be chosen. w[i] is weight i, x[i] is 1 when weight [i] is chosen. In the subset method there are two main decision branches:

Weight k is chosen:

// adding value of weight k to computed sum (cs) gives required sum, solution found
if(cs+w[k]==d)
{
cout<<"\n\nSolution "<<++count<<" is:";
for(i=0;i<=k;i++)
    if(x[i]==1)
    cout<<w[i]<<" ";
}

// both weight k and weight k+1 can be chosen without exceeding d, 
// so we choose k, and see if there's a solution for weight k+1 onwards
// note that available weight values decreased from r to r-w[k]
else if(cs+w[k]+w[k+1]<=d)
    subset(cs+w[k],k+1,r-w[k]);

Weight k is not chosen (notice that this is explored even when a solution was found right after weight k is chosen):

// weight k+1 is choosable (does not exceed d), and despite not choosing weight k
// there would be sufficient weights in r less w[k], and together with the chosen 
// pool cs to meet the requirement of d.
if(cs+w[k+1]<=d && cs+r-w[k]>=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}

Answer 3

Try this one.

#include<iostream>

int n,d,w[10],used[10],count=0;
int cs = 0; // cs=Current Sum

void subset(int k)
{
    if (k >= n) return;  // boundry check
    int i;
    used[k] = 1; // use element k
    cs += w[k];

    if(cs == d) {
        cout<<"\n\nSolution " << ++count << " is:"; 
        for(i=0;i <= k;i++)  
            if(used[i]==1) 
                cout<<w[i]<<" ";
    }
    if (cs < d)  // only when current sum is not enough
        subset(k + 1); 

    used[k] = 0; // not use element k
    cs -= w[k];
    subset(k+1);
}

void main()
{
    int sum=0,i;

    cout<<"enter n\n";
    cin>>n;

    cout<<"enter "<<n<<" elements\n";
    for(i=0;i<n;i++)
    cin>>w[i];

    for(i=0;i<n;i++)
    sum+=w[i];

    cout<<"enter value of sum\n";
    cin>>d;
    cs = 0;
    if(sum<d)
        cout<<"INVALID SOLUTION\n";
    else
        subset(0);
}