All Dictionary Segmentations

You are given a string s and an array words of distinct strings. A segmentation of s is a sequence of strings from words, each usable any number of times, whose concatenation equals s exactly.

Return every segmentation of s, each written as its pieces joined by single spaces. The segmentations may be returned in any order. If s has no segmentation, return an empty array.

Examples

Example 1

Input: s = "catsanddog", words = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Explanation: The pieces cats+and+dog and cat+sand+dog both concatenate to s.

Example 2

Input: s = "pineapplepenapple", words = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: A word may be reused: "apple" appears twice in the first segmentation.

Example 3

Input: s = "catsandog", words = ["cats","dog","sand","and","cat"]
Output: []
Explanation: No sequence of the given words concatenates to s.