title: Algorithm to find all combinations of a string, maintain order, not fixed length
body: <p>I would like to find all combinations of a string, maintaining order, but of any length. For example:</p>
  
  <pre><code>string_combinations("wxyz")
  # =&gt; ['w', 'wx', 'wxy', 'wxyz', 'wxz', 'wy', 'wyz', 'wz', 'x', 'xy', 'xyz', 'xz', 'y', 'yz', 'z']
  </code></pre>
  
  <p>I would prefer if you could use loops only and avoid using ruby methods like <code>#combination</code> as I am trying to find the cleanest way to implement this if I come across it in another language.</p>
  
  <p>Is there a way to do this in less than O(n^3)? My initial thought is something like:</p>
  
  <pre><code>def string_combinations(str)
      result = []
  
      (0...str.length).each do |i|
          result &lt;&lt; str[i]
          ((i+1)...str.length).each do |j|
              result &lt;&lt; str[i] + str[j]
              ((j+1)...str.length).each do |k|
                  result &lt;&lt; str[i] + str[j..k]
                  # Still not covering everything.
              end
          end
      end
  
      result
  end
  </code></pre>