Given a string s and a dictionary of words dict of length n, add spaces in s to construct a sentence where each word is a valid dictionary word. Each dictionary word can be used more than once. Return all such possible sentences.
Follow examples for better understanding.
Example 1:
Input: s = "catsanddog", n = 5 
dict = {"cats", "cat", "and", "sand", "dog"}
Output: (cats and dog)(cat sand dog)
Explanation: All the words in the given 
sentences are present in the dictionary.
Example 2:
Input: s = "catsandog", n = 5
dict = {"cats", "cat", "and", "sand", "dog"}
Output: Empty
Explanation: There is no possible breaking 
of the string s where all the words are present 
in dict.
Your Task:
You do not need to read input or print anything. Your task is to complete the function wordBreak() which takes n, dict and s as input parameters and returns a list of possible sentences. If no sentence is possible it returns an empty list.
Expected Time Complexity: O(N^{2}*n) where N = |s|
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ n ≤ 20
1 ≤ dict[i] ≤ 15
1 ≤ |s| ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Complete search

Starter code: #User function Template for python3



class Solution:

    def wordBreak(self, n, dict, s):

        # code here

Solutions:
class Solution:

	def search(self, word, dict):
		if word in dict:
			return True
		return False

	def solve(self, start, end, s, word_map, words, ans):
		if start > end:
			ans.append(words[:])
			return
		for i in range(start, end + 1):
			if word_map.get(s[start:i + 1]):
				words.append(s[start:i + 1])
				self.solve(i + 1, end, s, word_map, words, ans)
				words.pop()

	def solve(self, start, s, word_map, words, ans):
		if start == len(s):
			ans.append(words[:-1])
			return
		for i in range(start, len(s)):
			if word_map.get(s[start:i + 1]):
				self.solve(i + 1, s, word_map, words + s[start:i + 1] + ' ', ans)

	def wordBreak(self, n, dict, s):
		ans = []
		words = []
		word_map = {word: 1 for word in dict}
		self.solve(0, s, word_map, '', ans)
		return ans


class Solution:

	def search(self, word, dict):
		if word in dict:
			return True
		return False

	def solve(self, start, end, s, dict, words, ans):
		if start > end:
			ans.append(words[:])
			return
		for i in range(start, end + 1):
			if self.search(s[start:i + 1], dict):
				words.append(s[start:i + 1])
				self.solve(i + 1, end, s, dict, words, ans)
				words.pop()

	def wordBreak(self, n, dict, s):
		ans = []
		words = []
		self.solve(0, len(s) - 1, s, dict, words, ans)
		ans = list(map(lambda x: ' '.join(x), ans))
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		ind = 0
		ans = ''
		res = []

		def getAns(ind, ans, res):
			if ind == len(s):
				res.append(ans)
				return
			for i in range(ind, len(s)):
				if s[ind:i + 1] in dict:
					getAns(i + 1, ans + ('' if ans == '' else ' ') + s[ind:i + 1], res)
		getAns(0, ans, res)
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		list = []
		sett = set(dict)
		Solution.traverse(0, list, s, sett, '')
		return list

	@staticmethod
	def traverse(index, list, s, sett, str):
		if index >= len(s):
			list.append(str)
		else:
			for i in range(index, len(s)):
				if s[index:i + 1] in sett:
					Solution.traverse(i + 1, list, s, sett, str + ('' if str == '' else ' ') + s[index:i + 1])


class Solution:

	def __init__(self):
		self.ans = []

	def wordBreak(self, n, dict, s):
		self.util(n, dict, list(s), [], [])
		return self.ans

	def util(self, n, dict, s, word, listOfWords):
		if s == [] and word == []:
			self.ans.append(' '.join(listOfWords))
			return
		if s == []:
			return
		word.append(s[0])
		if ''.join(word) in dict:
			listOfWords.append(''.join(word))
			self.util(n, dict, s[1:], [], listOfWords)
		if ''.join(word) in dict:
			listOfWords.pop()
		self.util(n, dict, s[1:], word, listOfWords)
		word.pop()
		return


class Solution:

	def util(self, s, d, ans):
		global a
		if len(s) == 0:
			a[ans] = 1
			return
		for k in range(1, len(s) + 1):
			if d.get(s[:k]) != None:
				if len(ans) == 0:
					self.util(s[k:], d, ans + s[:k])
				else:
					self.util(s[k:], d, ans + ' ' + s[:k])
		return

	def wordBreak(self, n, dict, s):
		d = {}
		global a
		a = {}
		ans = []
		for i in dict:
			d[i] = 1
		self.util(s, d, '')
		for i in a.keys():
			ans.append(i)
		return ans


class Solution:

	def wordBreak(self, n, dict, s):

		def solve(arr, st, l, res):
			if st == len(s):
				res.append(l[:])
			for word in arr:
				if s[st:st + len(word)] == word:
					l.append(word)
					solve(arr, st + len(word), l, res)
					l.pop()
		res = []
		solve(dict, 0, [], res)
		res = [' '.join(x) for x in res]
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		res = []

		def backtrack(pos, sub, s):
			if pos == len(s):
				copy = ' '.join(sub)
				res.append(copy)
				return
			for idx in range(pos, len(s)):
				temp = s[pos:idx + 1]
				if temp not in dict:
					continue
				sub.append(temp)
				backtrack(idx + 1, sub, s)
				sub.pop()
		backtrack(0, [], s)
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		memo = {}

		def wordBreakHelper(s):
			if s in memo:
				return memo[s]
			if not s:
				return []
			result = []
			for word in dict:
				if s.startswith(word):
					if len(word) == len(s):
						result.append(word)
					else:
						suffix = s[len(word):]
						suffixSentences = wordBreakHelper(suffix)
						for sentence in suffixSentences:
							result.append(word + ' ' + sentence)
			memo[s] = result
			return result
		return wordBreakHelper(s)


class Solution:

	def wordBreak(self, n, dict, s):
		ans = []

		def func(i, st):
			if i == len(s):
				ans.append(st[:-1])
				return
			for j in range(i, len(s) + 1):
				if s[i:j] in dict:
					func(j, st + s[i:j] + ' ')
		func(0, '')
		return ans


class Solution:

	def __init__(self):
		self.ans = []

	def wordBreak(self, n, Dict, s):
		l = len(s)
		dp = [0] * l
		for i in range(l):
			arr = []
			for j in range(i + 1, l + 1):
				if s[i:j] in Dict:
					arr.append(s[i:j])
			dp[i] = arr
		sol = [0] * l
		for i in range(l - 1, -1, -1):
			ans = []
			if dp[i]:
				for word in dp[i]:
					if i + len(word) == l:
						ans.append(word)
					elif sol[i + len(word)]:
						for w in sol[i + len(word)]:
							ans.append(word + ' ' + w)
			sol[i] = ans
		return sol[0]


class trieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False

class trie:

	def __init__(self):
		self.root = trieNode()

	def insert(self, word):
		r = self.root
		cnt = 1
		for i in word:
			if r.children[ord(i) - ord('a')] == None:
				r.children[ord(i) - ord('a')] = trieNode()
			r = r.children[ord(i) - ord('a')]
			if cnt == len(word):
				r.isEnd = True
			cnt += 1

def solver(root, string, ans, curr, i):
	r = root
	if i >= len(string):
		ans.append(curr.strip())
	s = ''
	while i < len(string):
		if root != None:
			s += string[i]
			if root.children[ord(string[i]) - ord('a')] and root.children[ord(string[i]) - ord('a')].isEnd:
				solver(r, string, ans, curr + ' ' + s, i + 1)
		else:
			break
		root = root.children[ord(string[i]) - ord('a')]
		i += 1

class Solution:

	def wordBreak(self, n, dictionary, s):
		T = trie()
		for i in dictionary:
			T.insert(i)
		ans = []
		solver(T.root, s, ans, '', 0)
		return ans


def word_break_util(input_string, result_arr: [], input_dict: {}, output_string):
	if len(input_string) == 0:
		if output_string != '':
			result_arr.append(output_string)
		return
	n = len(input_string)
	for i in range(0, n):
		word = input_string[0:i + 1]
		if word in input_dict:
			word_break_util(input_string[i + 1:], result_arr, input_dict, output_string + str(word) + '-')

def word_break_main(input_string: [], input_dict: {}):
	result_arr = []
	word_break_util(input_string, result_arr, input_dict, '')
	final_arr = []
	for data in result_arr:
		result_words = data.split('-')[:-1]
		final_arr.append(' '.join(result_words))
	return final_arr

class Solution:

	def wordBreak(self, n, dict, s):
		return word_break_main(s, dict)


class Solution:

	def wordBreak(self, n, dict, s):
		return self.break_sentence(dict, s)

	def break_sentence(self, words, sentence, slist=None, collect=None):
		if slist is None:
			slist = []
		if collect is None:
			collect = []
		if len(sentence) == 0:
			collect.append(' '.join(slist))
			return
		for i in range(1, len(sentence) + 1):
			if sentence[:i] in words:
				slist.append(sentence[:i])
				self.break_sentence(words, sentence[i:], slist, collect)
				slist.pop()
		return collect


class Node:

	def __init__(self, val):
		self.val = val
		self.children = [None for _ in range(26)]
		self.eow = False

class Trie:

	def __init__(self):
		self.root = Node(-1)

	def insert(self, word, node=None, i=0):
		if node is None:
			node = self.root
		c = word[i]
		o = ord(c) - ord('a')
		if node.children[o] is None:
			node.children[o] = Node(c)
		if i == len(word) - 1:
			node.children[o].eow = True
		else:
			self.insert(word, node.children[o], i + 1)

	def query(self, word, node=None, i=0):
		if node is None:
			node = self.root
		c = word[i]
		o = ord(c) - ord('a')
		if node.children[o] is None:
			return 2
		elif i < len(word) - 1:
			return self.query(word, node.children[o], i + 1)
		elif node.children[o].eow:
			return 0
		else:
			return 1

	def printVal(self, node=None, prefix=''):
		if node is None:
			node = self.root
		for child in node.children:
			if child is not None:
				self.printVal(child, prefix + ' ')

class Solution:

	def wordBreak(self, n, dic, s):
		trie = Trie()
		for word in dic:
			trie.insert(word)
		res = self.helper(s, trie)
		return res

	def helper(self, s, trie, start=0):
		res = []
		for i in range(start + 1, len(s) + 1):
			word = s[start:i]
			query_res = trie.query(word)
			if query_res == 0:
				if i == len(s):
					res.append(word)
					return res
				for sub_res in self.helper(s, trie, i):
					res.append(word + ' ' + sub_res)
			elif query_res == 1:
				continue
			else:
				break
		return res


class Solution:

	def solve(self, ans, curr, i, dict, s):
		temp = s[:i]
		if i == len(s):
			if temp in dict:
				ans.append(' '.join(curr + [temp]))
			return
		if temp not in dict:
			self.solve(ans, curr, i + 1, dict, s)
			return
		curr.append(temp)
		self.solve(ans, curr, 0, dict, s[i:])
		curr.pop()
		self.solve(ans, curr, i + 1, dict, s)
		return

	def wordBreak(self, n, dict, s):
		ans = []
		curr = []
		self.solve(ans, curr, 0, dict, s)
		return ans


def func(s, dic, temp, ans):
	if not s:
		ans.append(temp[:])
		return
	for i in range(1, len(s) + 1):
		if s[:i] in dic:
			func(s[i:], dic, temp + [s[:i]], ans)

class Solution:

	def wordBreak(self, n, dic, s):
		ans = []
		func(s, dic, [], ans)
		re = []
		for i in ans:
			re.append(' '.join(i))
		return re


class Solution:

	def wordBreak(self, n, dictionary, line):
		dic = {}
		for i in dictionary:
			dic[i] = 1

		def manu(dic, word, f, a):
			if word == '':
				a.append(' '.join(f))
				return True
			x = False
			for i in range(len(word)):
				if word[:i + 1] in dic:
					f.append(word[:i + 1])
					x = manu(dic, word[i + 1:], f, a) or x
					f.pop()
			return x
		a = []
		manu(dic, line, [], a)
		return a


class Solution:

	def wordBreak(self, n, dict, s):
		dict_set = set(dict)
		dp = [False] * (len(s) + 1)
		dp[0] = True
		for i in range(1, len(s) + 1):
			for j in range(i):
				if dp[j] and s[j:i] in dict_set:
					dp[i] = True
					break
		res = []
		self.backtrack(s, len(s), dict_set, [], res, dp)
		return res

	def backtrack(self, s, end, dict_set, path, res, dp):
		if end == 0:
			res.append(' '.join(path[::-1]))
			return
		for i in range(end):
			if dp[i]:
				word = s[i:end]
				if word in dict_set:
					path.append(word)
					self.backtrack(s, i, dict_set, path, res, dp)
					path.pop()


class Solution:

	def wordBreak(self, n, dict, s):
		wordset = set(dict)
		res = []

		def word(ind=0, path=[]):
			if ind == len(s):
				res.append(' '.join(path))
			for j in range(ind + 1, len(s) + 1):
				words = s[ind:j]
				if words in wordset:
					word(j, path + [words])
		word()
		return res


class Solution:

	def wordBreak(self, n, d, s):

		def WordBreak(indx, n, dict, s, curr, ans):
			if indx == n:
				ans.append(curr)
				return
			str = ''
			for i in range(indx, n):
				str += s[i]
				if str in dict:
					ch = ''
					if i + 1 != n:
						ch = ' '
					WordBreak(i + 1, n, dict, s, curr + str + ch, ans)
		dict = {}
		for i in range(n):
			dict[d[i]] = True
		ans = []
		WordBreak(0, len(s), dict, s, '', ans)
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		N = len(s)
		dp = [[] for i in range(N + 1)]
		dp[0].append('')
		for i in range(1, N + 1):
			temp = ''
			lis = []
			for j in range(i, 0, -1):
				temp = s[j - 1] + temp
				if temp in dict:
					for k in dp[j - 1]:
						lis.append(k + ' ' + temp)
			dp[i].extend(lis)
		ans = []
		for i in dp[N]:
			ans.append(i[1:])
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		n = len(s)
		res = []

		def rec(i=0, curr=[]):
			if i >= n:
				res.append(' '.join(curr))
			temp = ''
			for idx in range(i, n):
				temp += s[idx]
				if temp in dict:
					curr.append(temp)
					rec(idx + 1, curr)
					curr.pop()
			return
		rec()
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		dic = {}
		for ele in dict:
			dic[ele] = 1
		ans = []
		li = []
		self.helper(dic, s, ans, li, len(s))
		return ans

	def helper(self, dic, s, ans, li, l):
		if l == 0:
			ans.append(' '.join((ele for ele in li)))
			return
		for i in range(1, l + 1):
			(left, right) = (s[:i], s[i:])
			if left in dic:
				li.append(left)
				self.helper(dic, right, ans, li, len(right))
				li.pop()
		return


class Solution:

	def word_machingII(self, str1, dict1, st, res, list1):
		if st == len(str1):
			res.append(list1[:-1])
			return
		for end in range(st, len(str1) + 1):
			if str1[st:end] in dict1:
				self.word_machingII(str1, dict1, end, res, list1 + str1[st:end] + ' ')

	def wordBreak(self, n, dict, s):
		res = []
		dict1 = set(dict)
		st = 0
		list1 = ''
		self.word_machingII(s, dict1, st, res, list1)
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		mp = set()
		for i in dict:
			mp.add(i)
		res = []

		def findsent(i, st, sent, s, mp):
			if i >= len(s):
				if st == '':
					res.append(sent)
				return
			if st + s[i] in mp:
				if len(sent) > 0:
					findsent(i + 1, '', sent + ' ' + st + s[i], s, mp)
				else:
					findsent(i + 1, '', st + s[i], s, mp)
			findsent(i + 1, st + s[i], sent, s, mp)
		findsent(0, '', '', s, mp)
		return res


class Solution:
	sents = []

	def wordBreak(self, n, dictionary, line):
		self.sents = []
		r = ''
		self.sol(line, dictionary, 0, r)
		return self.sents

	def sol(self, line, dic, i, r):
		if i == len(line):
			if r[0] == ' ':
				r = r[1:]
			self.sents.append(r)
			return
		for j in dic:
			l = len(j)
			x = line[i:i + l].find(j)
			if x > -1:
				self.sol(line, dic, i + l, r + ' ' + j)


class Solution:

	def wordBreak(self, n, dict, s):

		def wordbreakUtil(ind, dict, s, temp):
			if ind == len(s):
				res.append(temp[:])
				return
			t = ''
			for i in range(ind, len(s)):
				t += s[i]
				if t in dict:
					temp.append(t)
					wordbreakUtil(i + 1, dict, s, temp)
					temp.pop()
			return
		res = []
		wordbreakUtil(0, dict, s, [])
		ans = []
		for x in res:
			ans.append(' '.join(x))
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		dp = {}

		def word_break(s):
			if s in dp:
				return dp[s]
			res = []
			for word in dict:
				if s[:len(word)] == word:
					if len(s) == len(word):
						res.append(s)
					else:
						tmp = word_break(s[len(word):])
						for t in tmp:
							res.append(word + ' ' + t)
			dp[s] = res
			return res
		return word_break(s)


class Solution:

	def wordBreak(self, n, d, s):
		ans = []
		m = len(s)
		flag = [[False for _ in range(m)] for _ in range(m)]
		for i in range(m):
			for j in range(m):
				if s[i:j + 1] in d:
					flag[i][j] = True

		def solve(start, ans, temp, m):
			if start >= m:
				ans.append(' '.join(temp.copy()))
				return
			for i in range(m):
				if flag[start][i] == True:
					temp.append(''.join(s[start:i + 1]))
					solve(i + 1, ans, temp, m)
					temp.pop()
			return
		temp = []
		solve(0, ans, temp, m)
		return ans


class Node:

	def __init__(self):
		self.map = {}
		self.isWord = False

class Trie:

	def __init__(self):
		self.head = Node()
		self.ans = []

	def insert(self, word):
		temp = self.head
		for i in word:
			if i not in temp.map:
				temp.map[i] = Node()
			temp = temp.map[i]
		temp.isWord = True

	def check(self, word, s=''):
		if not word:
			self.ans.append(s.strip())
			return
		temp = self.head
		for i in range(len(word)):
			if word[i] in temp.map:
				temp = temp.map[word[i]]
				if temp.isWord:
					self.check(word[i + 1:], s + ' ' + word[:i + 1])
			else:
				return
		return

class Solution:

	def wordBreak(self, n, wordDict, s):
		trie = Trie()
		for word in wordDict:
			trie.insert(word)
		trie.check(s)
		return trie.ans


class Solution:

	def wordBreak(self, n, store, s):
		return self.helper(s, store, '')

	def helper(self, s, store, output):
		if not s:
			return [output[:-1]]
		result = []
		for item in store:
			n = len(item)
			if s[:n] == item:
				result += self.helper(s[n:], store, output + s[:n] + ' ')
		return result


class Solution:

	def wordBreak(self, n, dict, s):
		res = []

		def backtrack(bag, s_):
			nonlocal res
			if len(s_) == 0:
				res.append(' '.join(bag[:]))
				return
			for i in range(0, len(s_)):
				prefix = str(s_[:i + 1])
				if prefix in dict:
					suffix = s_[i + 1:]
					bag.append(prefix)
					backtrack(bag, suffix)
					bag.pop()
		s_ = s
		backtrack([], s_)
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		n = len(s)
		ans = []

		def solve(idx, curr, n):
			if idx == n:
				ans.append(' '.join(curr.copy()))
				return
			for i in range(idx, n + 1):
				substr = s[idx:i + 1]
				if substr in dict:
					curr.append(substr)
					solve(i + 1, curr, n)
					curr.pop()
		solve(0, [], n)
		return ans


class Solution:

	def wordBreak(self, n, wordDict, s):
		return self.helper(s, wordDict, {})

	def helper(self, s, wordDict, memo):
		if s in memo:
			return memo[s]
		if not s:
			return []
		res = []
		for word in wordDict:
			if not s.startswith(word):
				continue
			if len(word) == len(s):
				res.append(word)
			else:
				resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
				for item in resultOfTheRest:
					item = word + ' ' + item
					res.append(item)
		memo[s] = res
		return res


class Solution:

	def solve(self, s, st, dict, ans):
		if len(s) == 0:
			ans.append(st[:len(st) - 1])
			return
		n = len(s)
		for i in range(n):
			left = s[:i + 1]
			if left in dict:
				right = s[i + 1:]
				self.solve(right, st + left + ' ', dict, ans)

	def wordBreak(self, n, dict, s):
		ans = []
		self.solve(s, '', dict, ans)
		return ans


l = []

class Solution:

	def f(self, s, ans, dict):
		if len(s) == 0:
			l.append(ans[:len(ans) - 1])
			return
		n = len(s)
		for i in range(n):
			left = s[:i + 1]
			if left in dict:
				right = s[i + 1:]
				self.f(right, ans + left + ' ', dict)

	def wordBreak(self, n, dict, s):
		for i in range(len(l)):
			l.pop()
		self.f(s, '', dict)
		return l


class Solution:

	def wordBreak(self, n, _dict, s):
		words = set(_dict)
		ans = []
		slen = len(s)

		def backtrack(starti, arr):
			nonlocal ans, s, slen, words
			if starti == slen:
				ans.append(' '.join(arr))
			for endi in range(starti, slen):
				if s[starti:endi + 1] in words:
					arr.append(s[starti:endi + 1])
					backtrack(endi + 1, arr)
					arr.pop()
		backtrack(0, [])
		return ans


class Solution:

	def wordBreak(self, n, dict, s):

		def _wordBreak(s, wordDict, start, cur, res):
			if start == len(s) and cur:
				res.append(' '.join(cur))
				return res
			for i in range(start, len(s)):
				word = s[start:i + 1]
				if word in wordDict:
					cur.append(word)
					_wordBreak(s, wordDict, i + 1, cur, res)
					cur.pop()
		res = []
		_wordBreak(s, dict, 0, [], res)
		return res


class Solution:

	def wordBreak(self, n, dict, s):

		def isSafe(c, i, k):
			if s[c:c + k] == i:
				return True
			return False
		l = []

		def wb(c, ans):
			if c == len(s):
				l.append(' '.join(ans))
				return
			for i in dict:
				k = len(i)
				if isSafe(c, i, k):
					ans.append(i)
					t = c + k
					if wb(t, ans):
						return True
					t = c - k
					ans.pop()
			return False
		wb(0, [])
		return l


class Solution:

	def wordBreak(self, n, dict, s):
		dp = {}

		def word_break(s):
			if s in dp:
				return dp[s]
			result = []
			for w in dict:
				if s[:len(w)] == w:
					if len(w) == len(s):
						result.append(w)
					else:
						tmp = word_break(s[len(w):])
						for t in tmp:
							result.append(w + ' ' + t)
			dp[s] = result
			return result
		return word_break(s)


class Solution:

	def wordBreak(self, n, dict, s):
		sentence = []
		sentences = []
		self.wordBreakUtil(s, 0, sentence, sentences, dict, len(s))
		sentences = [' '.join(word) for word in sentences]
		return sentences

	def wordBreakUtil(self, input, prev, sentence, sentences, dict, n):
		if prev == n:
			sentences.append(sentence[:])
			return True
		for i in range(prev, n + 1):
			if input[prev:i] in dict:
				sentence.append(input[prev:i])
				self.wordBreakUtil(input, i, sentence, sentences, dict, n)
				sentence.pop()
		return False


class Solution:

	def wordbreak(self, n, dict, s):
		if s == '':
			if self.temp == '':
				return
			self.ans.append(self.temp[:-1])
		for i in range(len(s)):
			if s[:i + 1] in dict:
				self.temp += s[:i + 1]
				self.temp += ' '
				self.wordbreak(n, dict, s[i + 1:])
				self.temp = self.temp[:-1]
				self.temp = self.temp[:-(i + 1)]

	def wordBreak(self, n, dict, s):
		self.ans = []
		self.temp = ''
		self.wordbreak(n, dict, s)
		return self.ans


class Solution:

	def wordBreak(self, n, dict, s):
		self.sentences = []
		self.dict = set(dict)
		self.s = s
		self.n = len(s)
		self.makeSentences(0, '', [])
		return self.sentences

	def makeSentences(self, index, word, sentence):
		if index >= self.n:
			if word == '':
				self.sentences.append(' '.join(sentence))
			return
		word += self.s[index]
		if word in self.dict:
			self.makeSentences(index + 1, '', sentence + [word])
		self.makeSentences(index + 1, word, sentence)


class Solution:

	def wordBreak(self, n, dict, s):

		def backtrack(s, n, dict, index, output):
			if index == len(s):
				result.append(' '.join(output))
				return
			for word in dict:
				if index + len(word) <= len(s) and s[index:index + len(word)] == word:
					output.append(word)
					backtrack(s, n, dict, index + len(word), output)
					output.pop()
		result = []
		backtrack(s, n, dict, 0, [])
		return result


class Solution:

	def wordBreak(self, m, dic, s):
		global ans
		ans = []
		n = len(s)
		solve(dic, n, s, 0, '')
		return ans

def solve(dic, n, s, i, res):
	if i == n:
		ans.append(res.strip())
		return
	for j in range(i, n):
		wd = s[i:j + 1]
		if wd in dic:
			solve(dic, n, s, j + 1, res + wd + ' ')


class Solution:

	def wordBreak(self, n, dict, s):

		def func(ind, nn, res, ans, dict):
			if ind == nn:
				res.append(ans[:-1])
				return
			for i in range(ind, nn + 1):
				if s[ind:i] in dict:
					func(i, nn, res, ans + s[ind:i] + ' ', dict)
		res = []
		ans = ''
		nn = len(s)
		dict = set(dict)
		func(0, nn, res, ans, dict)
		return res


class Solution:

	def wordBreak(self, n, dict, s):
		d = {}
		for i in dict:
			d[i] = d.get(i, 0) + 1
		final = []
		temp = ''
		self.solutions(s, d, n, final, temp)
		return final

	def solutions(self, s, d, n, final, temp):
		if s == '':
			final.append(temp[:-1])
			return
		for i in range(len(s)):
			if d.get(s[:i + 1], 0) != 0:
				self.solutions(s[i + 1:], d, n, final, temp + s[:i + 1] + ' ')


def words(dict, s, cur, ans):
	if s == '':
		ans.append(cur[0:len(cur) - 1])
	for i in range(1, len(s) + 1):
		if s[0:i] in dict:
			words(dict, s[i:], cur + s[0:i] + ' ', ans)

class Solution:

	def wordBreak(self, n, dict, s):
		ans = []
		words(dict, s, '', ans)
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		ans = []

		def recurbreak(string, m, result):
			for i in range(1, m + 1):
				prefix = string[:i]
				if prefix in dict:
					if i == m:
						result += prefix
						ans.append(result)
						return
					recurbreak(string[i:], m - i, result + prefix + ' ')
		recurbreak(s, len(s), '')
		return ans


class Solution:

	def wordBreak(self, n, d, s, till=[]):
		if s == '':
			return [' '.join(till)]
		re = []
		for x in range(1, len(s) + 1):
			select = s[:x]
			if select in d:
				re += self.wordBreak(n, d, s[x:], [*till, s[:x]])
		return re


class Solution:

	def wordBreak(self, n, dict, s):
		output = []
		wordDict = dict

		def dfs(i, str):
			if i == len(s):
				output.append(str[:-1])
				return
			for j in range(i, len(s) + 1):
				if s[i:j] in wordDict:
					dfs(j, str + s[i:j] + ' ')
		dfs(0, '')
		return output


class Solution:

	def wordBreak(self, n, wordDict, s):
		ans = []

		def backtrack(idx, word, spaces):
			if idx == len(s) and len(word) - spaces == len(s):
				ans.append(word[1:])
				return
			if idx > len(s):
				return
			for w in wordDict:
				if idx + len(w) <= len(s):
					brokenWord = s[idx:idx + len(w)]
					if brokenWord == w:
						backtrack(idx + len(w), word + ' ' + brokenWord, spaces + 1)
			backtrack(idx + 1, word, spaces)
		backtrack(0, '', 0)
		return ans


class Solution:

	def wordBreak(self, n, words, s):
		ans = []
		rec(s, words, [], ans)
		return ans

def rec(s, words, acc, ans):
	if not s:
		ans.append(' '.join(acc))
		return
	for w in words:
		if s.startswith(w):
			acc.append(w)
			rec(s[len(w):], words, acc, ans)
			acc.pop()


class Solution:

	def wordBreak(self, n, dict, s):
		res = []
		path = []

		def backtrack(j):
			if j == len(s):
				res.append(' '.join(path))
			for i in range(n):
				wordLength = len(dict[i])
				if s[j:j + wordLength] != dict[i]:
					continue
				path.append(dict[i])
				backtrack(j + wordLength)
				path.pop()
		backtrack(0)
		return res


class Solution:
	ans_list = []

	def wordBreak(self, n, words, s):
		self.ans_list = []
		self.solve(words, s, '')
		return self.ans_list

	def solve(self, words, s, result_string):
		for word in words:
			result_string_copy = result_string
			if s == word:
				result_string_copy = result_string_copy + ' ' + word
				self.ans_list.append(result_string_copy.strip())
			if s.startswith(word):
				result_string_copy = result_string_copy + ' ' + word
				self.solve(words, s[len(word):], result_string_copy)


class Solution:

	def wordBreak(self, n, dic, s):
		m = len(s)
		l = [[True if j == 0 else False for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				x = len(dic[i - 1])
				if x > j:
					continue
				elif dic[i - 1] == s[j - x:j]:
					l[i][j] = True
		a = []

		def dfs(c, p):
			if c == 0:
				a.append(' '.join(p[::-1]))
				return
			for r in range(1, n + 1):
				if l[r][c]:
					p.append(dic[r - 1])
					dfs(c - len(dic[r - 1]), p)
					p.pop(-1)
		dfs(m, [])
		return a


def checkWordBreak(s, wordDict, idx, ans, arr):
	if idx == len(s):
		ans.append([] + arr)
		return
	for i in range(idx, len(s)):
		newStr = s[idx:i + 1]
		arr.append(newStr)
		if newStr in wordDict:
			checkWordBreak(s, wordDict, i + 1, ans, arr)
		arr.pop()
		newStr = s[:i + 1 - idx]

class Solution:

	def wordBreak(self, n, dict, s):
		ans = []
		checkWordBreak(s, dict, 0, ans, [])
		ansArr = []
		for i in range(len(ans)):
			tr = ''
			for j in range(len(ans[i])):
				if j != 0:
					tr += ' ' + ans[i][j]
				else:
					tr += ans[i][j]
			ansArr.append(tr)
		return ansArr


class Solution:

	def wordBreak(self, n, d, s):
		d = set(d)
		pre = set()
		for word in d:
			for i in range(1, len(word) + 1):
				pre.add(word[:i])

		def count(s):
			ans = []
			for i in range(1, len(s) + 1):
				word = s[:i]
				if word not in pre:
					break
				if word in d:
					if i == len(s):
						return ans + [word]
					l = count(s[i:])
					for sentence in l:
						ans.append(word + ' ' + sentence)
			return ans
		return count(s)


class Solution:

	def wordBreak(self, n, d, s):
		d = set(d)
		ans = []
		cans = []

		def rec(i, w):
			if i == len(s):
				if w == '':
					ans.append(' '.join(cans))
				return
			w1 = w + s[i]
			rec(i + 1, w1)
			if w1 in d:
				cans.append(w1)
				rec(i + 1, '')
				cans.pop()
		rec(0, '')
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		dict = set(dict)
		m = len(s)
		ans = []
		cans = []

		def rec(i, w):
			if i == m:
				if w == '':
					ans.append(' '.join(cans))
				return
			temp = w + s[i]
			if temp in dict:
				cans.append(temp)
				rec(i + 1, '')
				cans.pop()
			rec(i + 1, temp)
		rec(0, '')
		return ans


class Solution:

	def wordBreak(self, n, dict, s):

		def breakutil(s, x, res):
			for i in range(1, x + 1):
				if s[:i] in l:
					if i == x:
						ans.append(res + s[:i])
						return
					breakutil(s[i:], x - i, res + s[:i] + ' ')
		ans = []
		l = dict
		breakutil(s, len(s), '')
		return ans


class Solution:

	def wordBreak(self, n, dict, s):
		return self.explore(s, dict, {})

	def explore(self, target, wordbank, memo):
		if target == '':
			return ['']
		if target in memo:
			return memo[target]
		res = []
		for word in wordbank:
			if target.startswith(word):
				suffix = target[len(word):]
				suffix_ways = self.explore(suffix, wordbank, memo)
				for ways in suffix_ways:
					res.append(' '.join([word, ways]).strip())
		memo[target] = res
		return res


class Solution:

	def backtrack(self, comb, i, s, dict):
		if i == len(s):
			self.res.append(' '.join(comb))
			return
		for j in range(i, len(s)):
			cur_string = s[i:j + 1]
			if cur_string in dict:
				comb.append(cur_string)
				self.backtrack(comb, j + 1, s, dict)
				comb.pop(-1)

	def wordBreak(self, n, dict, s):
		self.res = []
		self.backtrack([], 0, s, dict)
		return self.res


class Solution:

	def wordBreak(self, n, dict, s):
		dictionary = {item: True for item in dict}
		dp = [list() for i in range(len(s))]
		for i in range(len(s)):
			word = ''
			for j in range(i, -1, -1):
				word = s[j] + word
				if dictionary.get(word):
					if j == 0:
						dp[i].append(word)
					elif dp[j - 1]:
						for sen in dp[j - 1]:
							new_sen = sen + ' ' + word
							dp[i].append(new_sen)
		return dp[len(s) - 1]


class Solution:

	def wordBreak(self, n, dicti, s):
		wordSet = set(dicti)
		res = []

		def backtrack(i, j, temp):
			if i == len(s) - 1 or j == len(s) - 1:
				if s[i:j + 1] in wordSet:
					z = temp + ' ' + s[i:j + 1]
					res.append(z[1:])
				else:
					return
			if s[i:j + 1] in wordSet:
				backtrack(j + 1, j + 1, temp + ' ' + s[i:j + 1])
			if j < len(s) - 1:
				backtrack(i, j + 1, temp)
		backtrack(0, 0, '')
		return res