Find all permutations of words from list that fits in given word

If I had the word "sometime" and I have the list of words

valid_words: ["some","time","rome","sometime","so","me"]

I want to output the result

result = [["so","me","time"],["some","time"],["sometime"]]

I know I should be using DFS, but I have no idea how to code it. I struggle with permutations. Can somebody help me?

This is what I have so far

def letterCombinations(word, valid_words):
    result = []
    def dfs(string_path, i, valid_word_set, curr_string):
      if i == len(word):
        return

      if string_path[:i] in valid_word_set:
        curr_string.append(string_path[:i])
        dfs(string_path[i:], i+1, valid_word_set, curr_string)
      else:
        dfs(string_path, i+1, valid_word_set, curr_string)
        
    for i in range(0, len(word)):
        if word[:i] in valid_words:
          curr_string = [word[:i]]
          dfs(word[i:], i, valid_words, curr_string)
          result.append(curr_string)
    
    return result

This should do the trick for you.
It uses recursion to loop through all the combinations and stores found words in set, so you are essentially caching

def letter_combos(word: str, word_dict: list[str]) -> list[list[str]]:
    def dfs(word: str, valid_word_set: set[str], start: int, memo: dict[int, list[list[str]]]) -> list[list[str]]:
        if start in memo:
            return memo[start]
        res: list[list[str]] = []
        if start == len(word):
            res.append([])
        for end in range(start + 1, len(word) + 1):
            if word[start:end] in word_dict:
                list_of_words = dfs(word, valid_word_set, end, memo)
                for lst in list_of_words:
                    res.append([word[start:end]] + lst)
        memo[start] = res
        return res
    return dfs(word, set(word_dict), 0, {})

word = "sometime"
valid_words = ["some", "time", "rome", "sometime", "so", "me"]

print(letter_combos(word, valid_words))

>>> [['so', 'me', 'time'], ['some', 'time'], ['sometime']]

You can also use functools lru_cache for this which tidies it up a bit

from functools import lru_cache

def letter_combos(word: str, valid_words: list[str]) -> list[list[str]]:
    @lru_cache(maxsize=None) 
    def dfs(start: int) -> list[list[str]]:
        if start == len(word):  
            return [[]]
        result: list[list[str]] = []
        for end in range(start + 1, len(word) + 1):
            if word[start:end] in valid_word_set:
                for lst in dfs(end):
                    result.append([word[start:end]] + lst)
        return result

    valid_word_set = set(valid_words)
    return dfs(0)

word = "sometime"
valid_words = ["some", "time", "rome", "sometime", "so", "me"]
print(letter_combos(word, valid_words))

Alternative solution basing on itertools.permutations and generator function:

from itertools import permutations

def match_perms(word, valid_words):
    words = valid_words[:]
    if word in words:   # if the whole word is found in words list
        yield (word,)
        words.remove(word)  # excude it from permutations

    for i in range(2, len(words)):
        for p in permutations(words, i):
            if ''.join(p) == word:
                yield p

print(list(match_perms(word, valid_words)))

[('sometime',), ('some', 'time'), ('so', 'me', 'time')]

A recursive approach, which also takes into account potential duplicated words using Counter:

from collections import Counter

word = 'sometime'
valid_words = ['some', 'time', 'rome', 'sometime', 'so', 'me']

def find_comb(word, valid_words, stem=None):
    if stem is None:
        stem = []
    if not isinstance(valid_words, Counter):
        valid_words = Counter(valid_words)
    if word in valid_words:
        yield stem + [word]
    for w in valid_words:
        if word.startswith(w):
            yield from find_comb(word[len(w):],
                                 valid_words-Counter({w: 1}),
                                 stem=stem+[w])  
    
out = list(find_comb(word, valid_words))

Output: [['sometime'], ['some', 'time'], ['so', 'me', 'time']]

Other examples:

list(find_comb('banana', ['banana', 'ba', 'na', 'na', 'nana']))
# [['banana'], ['ba', 'nana'], ['ba', 'na', 'na']]

list(find_comb('banana', ['banana', 'ba', 'na', 'nana']))
# [['banana'], ['ba', 'nana']]

def letterCombinations(word, valid_words):
      result = []

    
    def dfs(string_path, valid_word_set, curr_string):
        if not string_path:
            result.append(curr_string[:])  # Append a copy of the current string to the result list
            return
        
        for i in range(1, len(string_path) + 1):
            if string_path[:i] in valid_word_set:
                curr_string.append(string_path[:i])
                dfs(string_path[i:], valid_word_set, curr_string)
                curr_string.pop()  # Backtrack by removing the last element from the current string
    
       valid_word_set = set(valid_words)
       dfs(word, valid_word_set, [])
       return result

    word = "sometime"
    valid_words = ["some", "time", "rome", "sometime", "so", "me"]
    result = letterCombinations(word, valid_words) 
    print(result)

I think this will work for you let me know if it will not work