Word Break Problem Statement

You are provided with a continuous non-empty string (referred to as 'sentence') which contains no spaces and a dictionary comprising a list of non-empty strings (known as 'words'). Your task is to generate and return all conceivable sentences by inserting spaces within the original 'sentence', ensuring each word in the formed sentences originates from the provided dictionary.

Note:

The same word from the dictionary can be utilized multiple times to form the sentences.

Input:

The first line contains an integer ‘N’ representing the size of the dictionary.
Each of the following ‘N’ lines contains a non-empty string representing 'words' in the dictionary.
The ‘(N+1)’th line contains a non-empty string without spaces, representing the 'sentence'.

Output:

For each valid sentence, print it on a new line.

Example:

Input:

N = 4
words = ["cat", "cats", "and", "sand", "dog"]
sentence = "catsanddog"

Output:

"cats and dog"
"cat sand dog"

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 16
• 1 ≤ W ≤ 16
• Where ‘N’ is the length of the dictionary, ‘W’ is the length of a ‘word’ in the dictionary, and ‘M’ is the length of the 'sentence'.
• Time limit: 1 sec.