DIY: Word Break II

Problem statement

This challenge is an extension of the previous challenge. Again, you will be given a non-empty string s and a list of strings called subs. The subs list contains a unique set of strings. This time, you have to find a list of all the strings that can be created by breaking down string s into space-separated sequences of one or more strings from the subs list. A single string from subs can be reused multiple times in the breakdown of s.

Input

The first input will be a non-empty string called s, and the second input will be a list string called subs. The following is an example input:

magically
{"ag", "al", "icl", "mag", "magic", "ly", "lly"}

Output

The output will be a list of strings that contain all the possible strings that can be formed by breaking the string s in a space-separated sequence of strings from subs. The following is an example output:

['magic lly', 'mag icl ly']