How does this solution of the subset sum problem‍​​ work?

How does this solution of the subset sum problem‍​​ work?

• 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:

  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]); }