I am given a list of characters with repetitions, e.g. {"a", "a", "a", "c", "e", "e", "k", "m", "n", "s", "t"} and I need to find valid sentences built from these and only these letters, e.g. the sentence "man eats cake" is one such valid sentence for the list above. By "sentence" here I mean a string consisting of space-separated "words" and by "word" I mean any element of WordList[] or, even better, any syntactic variation for any root from WordList[].

So far, the only thing I was able to implement was this dynamical interactive interface which allows me to manually enter the test sentences and see what is left of my original list (stored in the variable "syms"):

Panel[DynamicModule[
  {try = ""},
  Column[
   {
    InputField[Dynamic[try], String, FieldSize -> Large],
    Dynamic[
     Fold[
      DeleteCases[##, 1, 1] &, syms, 
      Characters[ToLowerCase[try]] // Sort
      ]
     ]
    }
   ]
  ]
 ]

Even the above has a serious flaw: it doesn't detect letters not in the list (but that can be easily done) and doesn't detect trying to remove more instances of a letter than present in the list (and this can also be overcome). I didn't bother fixing these two bugs as I think it should be possible to approach this problem more properly, i.e. as stated in the first paragraph above.