title: Split string into words
body: <p>I am looking for the most efficient algorithm to form all possible combinations of words from a string. For example:</p>
  
  <pre><code>Input String: forevercarrot
  
  Output:
  
  forever carrot
  forever car rot
  for ever carrot
  for ever car rot
  </code></pre>
  
  <p>(All words should be from a dictionary).</p>
  
  <p>I can think of a brute force approach. (find all possible substrings and match) but what would be better ways?</p>