def generate_combinations(s, word_dict):
    def backtrack(start, current):
        if start == len(s):
            combinations.append(current.strip())
            return

        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_dict:
                new_current = current + ("" if current == "" else ", ") + word
                backtrack(end, new_current)

    combinations = []
    backtrack(0, "")
    return combinations


def print_possible_combinations(s, word_dict):
    combinations = generate_combinations(s, word_dict)

    if combinations:
        print("The input string can be segmented as [" + ", ".join(combinations) + "]")
    else:
        print("No possible combinations")
def word_break(s, word_dict):
    n = len(s)
    # Create set of words from list so that the lookup cost in dictionary becomes O(1)
    word_set = set(word_dict)

    # Initialize the lookup table
    dp = [False]*(n+1)

    # Setting the first element to True as it represents the empty string
    dp[0] = True

    for i in range(1, n+1):
        for j in range(i):
            # Checking if the substring from j to i is present in the wordDict and dp[j] is true
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                # If a substring is found, no need to check further smaller substrings
                break
    
    # Return the last element of dp list
    return dp[n]

# Driver Code
def main():

    s = ["vegancookbook", "catsanddog", "highwaycrash",
         "pineapplepenapple", "screamicecream", "educativecourse"]
    word_dict = ["ncoo", "kboo", "inea", "icec", "ghway", "and", "anco", "hi", "way", "wa",
                 "amic", "ed", "cecre", "ena", "tsa", "ami", "lepen", "highway", "ples",
                 "ookb", "epe", "nea", "cra", "lepe", "ycras", "dog", "nddo", "hway",
                 "ecrea", "apple", "shp", "kbo", "yc", "cat", "tsan", "ganco", "lescr",
                 "ep", "penapple", "pine", "book", "cats", "andd", "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\nInput: '" + str(s[i])+"'\n")
        print_possible_combinations(s[i], word_dict)
        print("\nOutput: " + str(word_break(str(s[i]), word_dict)))
        print("-" * 100)

if __name__ == '__main__':
    main()