def decouper_chaine(chaine, dictionnaire, memo={}):
    if chaine in memo:
        return memo[chaine]

    if chaine == "":
        return [[]]

    resultats = []
    for i in range(1, len(chaine) + 1):
        prefixe = chaine[:i]
        if prefixe in dictionnaire:
            for suffixe_decoupe in decouper_chaine(chaine[i:], dictionnaire, memo):
                resultats.append([prefixe] + suffixe_decoupe)

    memo[chaine] = resultats
    return resultats


dictionnaire = {"chat", "chapeau", "au", "lait", "laitue", "eau", "tue", "lai"}
chaine = "chapeaulaitueau"
decoupes = decouper_chaine(chaine, dictionnaire)
print("Découpes possibles :", decoupes)