title: How does this solution of the subset sum problem work?
body: <p>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. </p>
  
  <p>edit:I have added some comments to the code based on what i have understood. Please correct me if i am wrong.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  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&lt;&lt; "\n\nSolution " &lt;&lt; ++count &lt;&lt; " is:"; 
          for(i=0; i&lt;=k; i++)  // so if the subset criteria are met then the array is printed.
          if(x[i] == 1) 
              std::cout &lt;&lt; w[i] &lt;&lt; " ";
      }
      else if(cs + w[k] + w[k+1] &lt;= 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] &lt;= d &amp;&amp; cs + r - w[k] &gt;= d) //else backtrack
      {
          x[k] = 0;
          subset(cs, k+1, r-w[k]);
      }
  }
  
  int main()
  {
      int sum=0, i;
  
      std::cout &lt;&lt; "enter n\n";
      std::cin &gt;&gt; n;
  
      std::cout &lt; &lt;"enter " &lt;&lt; n &lt;&lt; " elements\n";
      for(i=0; i&lt;n; i++)
          std::cin &gt;&gt; w[i];
  
      for(i=0; i&lt;n; i++)
          sum += w[i];
  
      std::cout &lt;&lt; "enter value of sum\n";
      std::cin &gt;&gt; d;
  
      if(sum &lt; d)
          std::cout&lt;&lt;"INVALID SOLUTION\n";
      else
          subset(0,0,sum);
  
  }
  </code></pre>
  
  <p>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.</p>