Given a list of word lists of size  M * N. The task is to return all sentences possible taking one word from a list at a time via recursion. 
Example 1:
Input: 
L = {{"you", "we"},
     {"have", "are"},
Output: 
{{you have}
{you are}
{we have}
{we are}}
Explanation:
Consider every every word from the list and form
sentences with every other words, taking one word from a list .
Note: You need to maintain the order of the sentences.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sentences() which takes a matrix of strings as input and returns a matrix of string containing all possible sentences.
Expected Time Complexity: O(M^{N})
Expected Auxiliary Space: O(M^{N})
 
Constraints:
1 <= M, N <= 6
'a' <= sentence[i][j] <= 'z'

Source: geeksforgeeks | Difficulty: EASY

Starter code: from typing import List





from typing import List





class Solution:

    def sentences(self, list : List[List[str]]) -> List[List[str]]:

        # code here

        



Solutions:
from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		ans = []

		def backtrack(i, curr):
			if i >= len(list):
				ans.append([curr.lstrip()])
				return
			for j in list[i]:
				curr = curr + ' ' + j
				backtrack(i + 1, curr)
				curr = curr[:-(len(j) + 1)]
		backtrack(0, '')
		return ans


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:

		def printallsentences(li):
			if len(li) == 1:
				subsentences = [[word] for word in li[0]]
				return subsentences
			else:
				subsentences = printallsentences(li[1:])
				sentences = []
				for item in li[0]:
					for word in subsentences:
						s = [item] + word
						sentences.append(s)
				return sentences
		result = printallsentences(list)
		return result


from typing import List
from typing import List
arr = []

def recur(list, i, s):
	global arr
	if i >= len(list):
		v = s.copy()
		arr.append(v)
		return 0
	for j in range(0, len(list[0])):
		s.append(list[i][j])
		recur(list, i + 1, s)
		s.pop()

class Solution:
	global arr

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		global arr
		recur(list, 0, [])
		return arr


class Solution:

	def sentences(self, list):

		def printallsentences(list):
			if len(list) == 1:
				return [[word] for word in list[0]]
			else:
				subsentences = printallsentences(list[1:])
				sentences = []
				for word in list[0]:
					for sentence in subsentences:
						sen = [word] + sentence
						sentences.append(sen)
				return sentences
		sentences = printallsentences(list)
		return sentences


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def helper(self, i, j, m, n, l, ans, temp):
		temp[i] = l[i][j]
		if i == m - 1:
			ans.append(temp[:])
			return
		for k in range(n):
			self.helper(i + 1, k, m, n, l, ans, temp)

	def sentences(self, l: List[List[str]]) -> List[List[str]]:
		ans = []
		m = len(l)
		n = len(l[0])
		for i in range(n):
			temp = [''] * m
			self.helper(0, i, m, n, l, ans, temp)
		return ans


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		res = []

		def come(i, temp):
			if i == len(list):
				res.append(temp)
				return
			for c in range(len(list[0])):
				if list[i][c] != '':
					come(i + 1, temp + [list[i][c]])
		come(0, [])
		return res


from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		resp = []
		self.solve(list, [], resp, 0)
		return resp

	def solve(self, list, tmp, resp, idx):
		if idx == len(list):
			resp.append(tmp[:])
			return
		for i in list[idx]:
			self.solve(list, tmp + [i], resp, idx + 1)


from typing import List
from typing import List

class Solution:

	def sentences(self, a: List[List[str]]) -> List[List[str]]:
		res = []
		(row, col) = (len(a), len(a[0]))

		def call(i, temp):
			if i == row:
				res.append(temp[:])
				return
			for j in range(col):
				temp.append(a[i][j])
				call(i + 1, temp)
				temp.pop()
		call(0, [])
		return res


from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		R = len(list)
		C = len(list[0])
		ans = []
		output = [0] * R

		def dfs(m, n, output):
			output[m] = list[m][n]
			if m == R - 1:
				ans.append(output[:])
				return
			for col in range(C):
				dfs(m + 1, col, output)
		for col in range(C):
			dfs(0, col, output)
		return ans


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		res = []
		for i in list[0]:
			res.append([i])
		temp = []
		for i in range(1, len(list)):
			r = []
			for j in range(len(res)):
				for k in list[i]:
					temp = res[j].copy()
					temp.append(k)
					r.append(temp)
			res = r
		return res


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		numRow = len(list)
		numCol = len(list[0])
		ans = []

		def solve(indexRow, sentence):
			if indexRow == numRow:
				temp = [i for i in sentence]
				ans.append(temp)
				return
			for j in range(numCol):
				sentence.append(list[indexRow][j])
				solve(indexRow + 1, sentence)
				sentence.pop()
		solve(0, [])
		return ans


from typing import List
from typing import List

class Solution:

	def solve(self, list1, i, n, out, ans):
		if i == n:
			ans.append(out[:])
			return
		for j in range(len(list1[i])):
			out.append(list1[i][j])
			self.solve(list1, i + 1, n, out, ans)
			out.pop()

	def sentences(self, list1: List[List[str]]) -> List[List[str]]:
		ans = []
		self.solve(list1, 0, len(list1), [], ans)
		return ans


from typing import List
from typing import List

class Solution:

	def solve(self, arr, ind, n, out):
		if ind == n:
			ans.append(out[:])
			return
		for i in range(len(arr[ind])):
			out.append(arr[ind][i])
			self.solve(arr, ind + 1, n, out)
			out.pop()

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		global ans
		ans = []
		self.solve(list, 0, len(list), [])
		return ans


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		res = []
		for i in list[0]:
			res.append([i])
		temp = []
		for i in range(1, len(list)):
			r = []
			for j in range(len(res)):
				for k in list[i]:
					temp = res[j].copy()
					temp.append(k)
					r.append(temp)
			res = r
		return res

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class StringMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([str(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	a = IntArray().Input(2)
	list = StringMatrix().Input(a[0], a[1])
	obj = Solution()
	res = obj.sentences(list)
	StringMatrix().Print(res)


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		N = len(list)
		M = len(list[0])
		ans = []

		def solve(index, sentence):
			if index == N:
				temp = [i for i in sentence]
				ans.append(temp)
				return
			for j in range(M):
				sentence.append(list[index][j])
				solve(index + 1, sentence)
				sentence.pop()
		solve(0, [])
		return ans

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class StringMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([str(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	a = IntArray().Input(2)
	list = StringMatrix().Input(a[0], a[1])
	obj = Solution()
	res = obj.sentences(list)
	StringMatrix().Print(res)


from typing import List
from typing import List

def func(gg, ans, l, i, j, temp):
	if i == len(l):
		ans.append(temp.copy())
		k = temp.copy()
		gg.append(k)
		return
	if j == len(l[0]):
		return
	temp.append(l[i][j])
	func(gg, ans, l, i + 1, 0, temp)
	temp.pop()
	func(gg, ans, l, i, j + 1, temp)

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		ans = []
		gg = []
		p = func(gg, ans, list, 0, 0, [])
		pp = []
		for i in ans:
			pp.append(' '.join(i))
		return gg

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class StringMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([str(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	a = IntArray().Input(2)
	list = StringMatrix().Input(a[0], a[1])
	obj = Solution()
	res = obj.sentences(list)
	StringMatrix().Print(res)


from typing import List
from typing import List

class Solution:

	def sentences(self, A: List[List[str]]) -> List[List[str]]:
		n = len(A)
		ans = []

		def solve(s, i):
			if i == n:
				ans.append(s)
				return
			else:
				if i == 0:
					for c in range(len(A[0])):
						solve([A[i][c]], i + 1)
					return
				for c in range(len(A[i])):
					solve(s + [A[i][c]], i + 1)
		solve([], 0)
		return ans


from typing import List
from typing import List

class Solution:

	def prints(self, list, r, R, C, sen, res):
		if r == R:
			res.append(sen)
			return
		for i in range(C):
			if list[r][i] != '':
				self.prints(list, r + 1, R, C, sen + ' ' + list[r][i], res)

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		res = []
		sen = ''
		self.prints(list, 0, len(list), len(list[0]), sen, res)
		op = []
		for i in res:
			op.append(i.split())
		return op


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		m = len(list)
		n = len(list[0])

		def cal(i, sen):
			if i >= m:
				temp = []
				for j in sen:
					temp.append(j)
				res.append(temp)
				return
			for k in range(n):
				sen[i] = list[i][k]
				cal(i + 1, sen)
		res = []
		sen = ['' for i in range(m)]
		cal(0, sen)
		return res


from typing import List
from typing import List

class Solution:
	ansmat = []

	def dfs(self, mat, i, j, ans):
		ans[i] = mat[i][j]
		r = len(mat)
		c = len(mat[i])
		if i == r - 1:
			temp = ans.copy()
			self.ansmat.append(temp)
			return
		if i + 1 < r:
			nc = len(mat[i + 1])
			for k in range(nc):
				self.dfs(mat, i + 1, k, ans)

	def sentences(self, mat: List[List[str]]) -> List[List[str]]:
		r = len(mat)
		c = len(mat[0])
		ans = [''] * r
		for i in range(c):
			self.dfs(mat, 0, i, ans)
		return self.ansmat


from typing import List
from typing import List

class Solution:

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		res = []
		s = []

		def dfs(i, j):
			if i == len(list) or j == len(list[0]):
				res.append(s.copy())
				return
			for k in range(len(list[0])):
				s.append(list[i][k])
				dfs(i + 1, k)
				s.pop()
		dfs(0, 0)
		return res


from typing import List

class Solution:

	def sentences(self, L: List[List[str]]) -> List[List[str]]:
		if len(L) == 1:
			result = []
			for word in L[0]:
				result.append([word])
			return result
		sents = self.sentences(L[1:])
		result = []
		for word in L[0]:
			for sent in sents:
				result.append([word] + sent)
		return result


from typing import List

class Solution:

	def sentences(self, l: List[List[str]]) -> List[List[str]]:
		ans = []
		n = len(l)

		def traverse(i, curr):
			if i == n:
				ans.append(curr.copy())
				return
			for x in l[i]:
				curr.append(x)
				traverse(i + 1, curr)
				curr.pop()
			return
		traverse(0, [])
		return ans


from typing import List

def printUtil(arr, m, n, output):
	output[m] = arr[m][n]
	if m == len(arr) - 1:
		for i in range(len(arr)):
			print(output[i], end=' ')
		print()
		return
	for i in range(len(arr[0])):
		if arr[m + 1][i] != '':
			printUtil(arr, m + 1, i, output)

class Solution:

	def sentences(self, arr: List[List[str]]) -> List[List[str]]:
		output = [''] * len(arr)
		m = len(arr)
		n = len(arr[0])
		for i in range(n):
			if arr[0][i] != '':
				printUtil(arr, 0, i, output)
		return [[]]


from typing import List

class Solution:

	def sentences(self, lis: List[List[str]]) -> List[List[str]]:
		final = []
		n = len(lis)

		def rec(ind=0, count=0, sentence=[]):
			nonlocal final, lis, n
			if count == n:
				final += [sentence]
				return
			for (i, words) in enumerate(lis):
				if i < ind:
					continue
				for word in words:
					rec(i + 1, count + 1, sentence + [word])
		rec()
		return final


from typing import List
from typing import List

class Solution:

	def getwords(self, n):
		if n == 0:
			return words[n]
		else:
			sentences = self.getwords(n - 1)
			sentences2 = []
			for x in sentences:
				for y in words[n]:
					sentences2.append(x + ' ' + y)
			return sentences2

	def sentences(self, list: List[List[str]]) -> List[List[str]]:
		global words
		words = list
		sent = self.getwords(len(list) - 1)
		sentence = [i.split() for i in sent]
		return sentence