word_break_II.py

def word_break(s: str, word_dict: List[str]) -> List[str]:
    word_dict, sentences, n = set(word_dict), [], len(s)

    def backtrack(start: int, cur: List[str]) -> None:
        if start == n: # solution valide, on la retient
            sentences.append(' '.join(cur))
            return

        for i in range(start + 1, n + 1):
            if s[start: i] in word_dict:
                # cette solution respecte les contraintes,
                # on peut continuer à explorer les solutions suivantes
                backtrack(i, cur + [s[start: i]])

    backtrack(0, [])

    return sentences