Concatenated Words with All Decompositions

Problem: Output All Decomposition Combinations of Concatenated Words Given a list of unique strings words, where each word consists of lowercase English letters. A word is called a concatenated word if it can be formed by concatenating at least two words from the given list in order. Find all concatenated words and output all their valid decomposition combinations. Rules Every component must be a word in words. The same word may be reused multiple times. A target word cannot be counted as a valid decomposition by using only itself; each valid decomposition must contain at least 2 components. The output must be deterministic: Output target words in lexicographical order. For the same target word, output decompositions in lexicographical order of the component lists. If no concatenated word exists, print EMPTY. Input Format n word_1 word_2 ... word_n Output Format For each concatenated word, print one line: target: part1+part2+... | part1+part2+... If there is no answer: EMPTY Constraints 1 <= n <= 2000 1 <= len(words[i]) <= 100 The total length of all words is at most 2 * 10^5. The total number of output combinations is guaranteed to be reasonable, e.g. at most 10^5. Example Input: 7 cat cats dog catsdog dogcatsdog rat ratcatdogcat Output: catsdog: cats+dog dogcatsdog: dog+cats+dog | dog+catsdog ratcatdogcat: rat+cat+dog+cat Example Input 7 cat cats dog catsdog dogcatsdog rat ratcatdogcat Output catsdog: cats+dog dogcatsdog: dog+cats+dog | dog+catsdog ratcatdogcat: rat+cat+dog+cat