Word Break Problem Statement

You are given a non-empty string without spaces, referred to as 'sentence', and a list of non-empty strings representing a dictionary. Your task is to construct and return all possible sentences by inserting spaces in the given 'sentence' such that each segmented word is found in the dictionary.

Note:

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

Input Format:

The first line contains an integer ‘N’ indicating the size of the dictionary.
Each of the next ‘N’ lines contains a non-empty string representing each word in the dictionary.
Following that, there is a single non-empty string representing the 'sentence'.

Output Format:

Output each possible sentence after adding spaces, each on a new line.

Note:

There is no need to print anything manually; output handling is already managed. The order of sentences does not matter.

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 16
• 1 ≤ W ≤ 16

Where ‘N’ is the number of dictionary words, ‘W’ is the length of a word in the dictionary, and ‘M’ is the length of the sentence. Time limit: 1 second.