title: How to improve recursive backtracking algorithm
body: <p>I implemented backtracking based solution for my problem which I specified in my previous post: <a href="https://stackoverflow.com/questions/8023113/packing-items-into-fixed-number-of-bins">Packing items into fixed number of bins</a></p>
  
  <p>(Bin is a simple wrapper for <code>vector&lt;int&gt;</code> datatype with additional methods such as sum() )</p>
  
  <pre class="lang-cpp prettyprint-override"><code>bool backtrack(vector&lt;int&gt;&amp; items, vector&lt;Bin&gt;&amp; bins, unsigned index, unsigned bin_capacity)
  {
      if (bin_capacity - items.front() &lt; 0) return false;
  
      if (index &lt; items.size())
      {
          //try to put an item into all opened bins
          for(unsigned i = 0; i &lt; bins.size(); ++i)
          {
              if (bins[i].sum() + items[index] + items.back() &lt;= bin_capacity || bin_capacity - bins[i].sum() == items[index])
              {
                  bins[i].add(items[index]);
                  return backtrack(items, bins, index + 1, bin_capacity);
  
              }
          }
          //put an item without exceeding maximum number of bins
          if (bins.size() &lt; BINS)
          {
              Bin new_bin = Bin();
              bins.push_back(new_bin);
              bins.back().add(items[index]);
  
              return backtrack(items, bins, index + 1, bin_capacity);
  
          }
      }
      else
      {
          //check if solution has been found
          if  (bins.size() == BINS )
          {
              for (unsigned i = 0; i &lt;bins.size(); ++i)
              {
                  packed_items.push_back(bins[i]);
              }
  
              return true;
          }
      }
      return false;
  }
  </code></pre>
  
  <p>Although this algorithm works quite fast, it's prone to stack overflow for large data sets.</p>
  
  <p>I'm looking for any ideas and suggestions how to improve it.</p>
  
  <p>Edit:</p>
  
  <p>I decided to try an iterative approach with explicit stack, but my solution doesn't work as expeced - sometimes it gives incorrect results.</p>
  
  <pre class="lang-cpp prettyprint-override"><code>bool backtrack(vector&lt;int&gt;&amp; items, vector&lt;Bin&gt;&amp; bins, unsigned index, unsigned bin_capacity)
  {
        stack&lt;Node&gt; stack;
        Node node, child_node;
        Bin new_bin;
        //init the stack
        node.bins.add(new_bin);
        node.bins.back().add(items[item_index]);
        stack.push(node);
        item_index++;
  
        while(!stack.empty())
        {
          node = stack.top();
          stack.pop();
  
          if (item_index &lt; items.size())
          {
              if (node.bins.size() &lt; BINS)
              {
                 child_node = node;
                 Bin empty;
                 child_node.bins.add(empty);
                 child_node.bins.back().add(items[item_index]);
                 stack.push(child_node);
              }
  
              int last_index = node.bins.size() - 1;
              for (unsigned i = 0; i &lt; node.bins.size(); i++)
              {
                  if (node.bins[last_index - i]-&gt;get_sum() + items[item_index]+ items.back() &lt;= bin_capacity || 
                  bin_capacity - node.bins[last_index - i]-&gt;get_sum() == items[item_index]) 
                 {
                     child_node = node;
                     child_node.bins[last_index - i]-&gt;push_back(items[item_index]);
                     stack.push(child_node);
                  }
              }
              item_index++;
              }
          else
          {
             if (node.bins() == BINS)
             {
                 //copy solution
                 bins = node.bins;
                 return true;
             }
         }
     }
      return false;
  }
  </code></pre>
  
  <p>Any suggestions are highly appreciated.</p>