Word Break II: All Possible Sentence Combinations From Dictionary

snapchat Given a dictionary and a target word, determine if the target can be constructed by concatenating words from the dictionary. Each word in the dictionary can be used multiple times. Return all possible combinations. Input: A string array dictionary representing the words in the dictionary. A string target representing the target word. For example: dictionary = ["cat", "cats", "and", "sand", "dog"], target = "catsanddog" Output: A list of strings representing all possible combinations, where each string is one way of combining the words. Example: Input: dictionary = ["cat", "cats", "and", "sand", "dog"], target = "catsanddog" Output: ["cats and dog", "cat sand dog"] Constraints: All inputs are lowercase letters. The total length of all words in dictionary does not exceed 1000. The length of target does not exceed 100. Example Input ['cat', 'cats', 'and', 'sand', 'dog'] catsanddog