title: Separating compound and simple words
body: <p>I know this problem is probably best served with DP, but I was wondering if it was possible to do it with recursion as a brute force way.</p>
  
  <p>Given a set of words, say {"sales", "person", "salesperson"}, determine which words are compound (that is, it is the combination of 2 or more words in the list). So in this case, salesperson = sales + person, and is compound. </p>
  
  <p>I based my answer heavily off of this problem: <a href="http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/" rel="nofollow">http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/</a></p>
  
  <pre><code>public static void main(String args[]) throws Exception {
  
      String[] test = { "salesperson", "sales", "person" };
      String[] output = simpleWords(test);
  
  
      for (int i = 0; i &lt; output.length; i++)
          System.out.println(output[i]);
  }
  
  static String[] simpleWords(String[] words) {
      if (words == null || words.length == 0)
          return null;
  
      ArrayList&lt;String&gt; simpleWords = new ArrayList&lt;String&gt;();
  
      for (int i = 0; i &lt; words.length; i++) {
          String word = words[i];
          Boolean isCompoundWord = breakWords(words, word);
  
          if (!isCompoundWord)
              simpleWords.add(word);
      }
  
      String[] retVal = new String[simpleWords.size()];
      for (int i = 0; i &lt; simpleWords.size(); i++)
          retVal[i] = simpleWords.get(i);
  
      return retVal;
  
  }
  
  static boolean breakWords(String[] words, String word) {
      int size = word.length();
  
      if (size == 0 ) return true;
  
      for (int j = 1; j &lt;= size; j++) {
  
          if (compareWords(words, word.substring(0, j)) &amp;&amp; breakWords(words, word.substring(j, word.length()))) {
              return true;
          }
      }
  
      return false;
  }
  
  static boolean compareWords(String[] words, String word) {
      for (int i = 0; i &lt; words.length; i++) {
          if (words[i].equals(word))
              return true;
      }
      return false;
  }
  </code></pre>
  
  <p>The problem here is now that while it successfully identifies salesperson as a compound word, it will also identify sales and person as a compound word. Can this code be revised so that this recursive solution works? I'm having trouble coming up with how I can easily do this.</p>