= Solution
Use <trie search with a letter multiset>. Counts avoid generating the same result repeatedly when the input contains equal letters. The <backtracking> explores a letter value once, irrespective of how many indistinguishable copies remain.
``
def allWords(ls: String): List[String] = {
val left = new Array[Int](26)
var i = 0
while (i < ls.length) {
left(toIndex(ls.charAt(i))) += 1
i += 1
}
var out = List.empty[String]
def visit(t: Trie, prefix: String): Unit = {
if (t.complete) out = prefix :: out
var k = 0
while (k < 26) {
val child = t.children(k)
if (left(k) > 0 && child != null) {
left(k) -= 1
visit(child, prefix + toChar(k))
left(k) += 1
}
k += 1
}
}
visit(this, "")
out.reverse
}
``
At entry to `visit`, `t` is reached by `prefix`, and `left(k)` is the input multiplicity of letter $k$ minus its multiplicity in `prefix`. All these counts are nonnegative. Each recursive call consumes one available letter, and restoration makes sibling calls see the same counts as before that child. The <recursion> therefore terminates at depth at most $|ls|$, even when the dictionary contains longer words.
A completed prefix is emitted once, and the traversal continues so that longer words with the same prefix are also found. Every emitted word is in the dictionary and uses at most the available multiplicities. Conversely, every dictionary word meeting those bounds has an existing <trie> path whose next letter has positive remaining count at every step; the traversal reaches its terminal node. A <trie> has a unique root path for each word, and each child is visited at most once per reached node. Therefore
$$
\boxed{out=\{w\in D:\forall c,\ \operatorname{count}_w(c)\leq\operatorname{count}_{ls}(c)\},\quad\text{without repetitions}.}
$$
The boxed expression specifies the <set> of entries in the returned <list>, rather than its ordering. If the dictionary includes the empty <string>, the method includes it once. Counting costs $O(|ls|+26)$; visiting $R$ reachable nodes costs $O(26R)$ apart from <string> copying and output construction. The presented immutable-prefix construction additionally costs the sum of the prefix lengths it constructs. The recursion depth is at most $|ls|$, and the letter-count <array> has fixed size.
Back to article page
