Word Break II Problem Statement

Given a non-empty string 'S' containing no spaces and a dictionary of non-empty strings, generate and return all possible sentences by adding spaces in the string 'S', such that each word in a sentence exists in the given dictionary.

Note:

The same word in the dictionary can be used multiple times to form sentences. Assume there are no duplicate words in the dictionary.

Input:

The first line contains an integer 'T' denoting the number of test cases.

Then the 'T' test cases follow.

The first line of each test case contains an integer 'K' which denotes the size of the dictionary.
The second line contains 'K' non-empty, space-separated strings denoting the words of the dictionary.
The third line contains a non-empty string 'S'.

Output:

For each test case, print each possible sentence after adding spaces, in different lines.

The output of each test case is printed in a separate line.

Note:

1. You do not need to print anything, it has already been taken care of. Just implement the given function.
2. The order in which the output sentences are returned does not matter.

Constraints:

• 1 <= T <= 10
• 1 <= K <= 100
• 1 <= |word| <= 16
• 1 <= |S| <= 13
• Time Limit: 1 sec