def word_break(s, word_dict):

    # Initializing the dp table of size s.length + 1
    dp = [[]] * (len(s) + 1)

    # Setting base case
    dp[0] = [""]

    # For each substring in the input string, repeat the process.
    for i in range(1, len(s) + 1):

        prefix = s[:i]

        # An array to store the valid sentences formed from the current prefix being checked.
        temp = []

        # Iterate over the current prefic and break it down into all possible suffixes.
        for j in range(0, i):
            suffix = prefix[j:]
            
            # Check if the current suffix exists in word_dict. If it does, we know that it is a valid word
            # and can be used as part of the solution.
            if suffix in word_dict:
                
                # Retrieve the valid sentences from the previously computed subproblem
                for substring in dp[j]:
                    # Merge the suffix with the already calculated results
                    temp.append((substring + " " + suffix).strip())

        dp[i] = temp

    # Returning all the sentences formed from the complete string s.
    return dp[len(s)]

# Driver Code
def main():

    s = ["vegancookbook", "catsanddog", "highwaycrash",
         "pineapplepenapple", "screamicecream", "educativecourse"]

    word_dict = ["oghi", "ncoo", "kboo", "inea",
        "icec", "ghway", "tsand", "anco", "eame", "ghigh", "hi", "way", "wa",
        "amic", "mi", "ed", "cecre", "pple", "reamicecreamed", "ena", "tsa", "ami", "hwaycrashpineapplepenapplescreamicecreamed", "lepen", "okca", "highway", "ples", "atsa", "oghig", "ookb", "epe", "ookca", "nea", "cra", "lepe", "vegancookbookcatsandd",
        "kc", "ra", "le", "ay", "crashpineapple", "ycras", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescre", "doghi", "nddo", "hway", "vegancookbookcatsanddoghi", "vegancookbookcatsanddoghighwaycr", "at", "mice", "nc", "d", "enapplescreamicecreamed", "h",
        "ecrea", "nappl", "shp", "kbo", "yc", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescream", "cat", "waycrashpineapplepenapplescreamicecreamed", "tsan", "vegancookbookcatsanddoghighwaycrashpineap", "ganco", "lescr", "sand", "applescreamicecreamed", "vegancookbookcatsanddoghig", "pi", "vegancookbookcatsanddoghighwaycrashpineapp", "cookb", "okcat", "neap", "nap", "oghighwaycrashpineapplepenapplescreamicecreamed", "crashpineapplepenapplescreamicecreamed",
        "ashpi", "ega", "escreamicecreamed", "hwa", "rash", "cre", "micecreamed", "plepe", "coo", "epen", "napp", "wayc", "vegancookbookcatsanddoghighwaycrashpinea", "vegancookbookcatsanddogh", "plep", "ice", "ple", "gh", "ghw", "cook", "pl", "app", "ic", "pinea", "hello", "dog", "vegancookbookcat", "eamed", "ook", "lesc", "ddog", "ca", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescreamice", "c", "escr", "penap", "boo", "eami", "ecreamed", "vegancookbookcatsanddoghighwaycrashpi", "igh", "mic", "ganc", "vegancookbookcatsanddoghighwaycrashpineapplepenap",
        "eappl", "vegancookbookcatsanddoghighway", "ep", "penapple", "b", "ycrashpineapplepenapplescreamicecreamed", "pin", "book", "p", "sa", "okb", "andd", "ayc", "sh", "vegan", "cookbook"]

    print("The list of words we can use to break down the strings are:\n\n", word_dict, "\n")
    print("-" * 100)
    for i in range(len(s)):
        print("Test Case #", i+1, "\n\nThe possible strings from the string '" +
              str(s[i]) + "' are the following combinations:", sep="")
        print("\n" + str(word_break(str(s[i]), word_dict)))
        print("-" * 100)

if __name__ == '__main__':
    main()