Given a string str your task is to complete the function spaceString which takes only one argument the string str and  finds all possible strings that can be made by placing spaces (zero or one) in between them. 
For eg .  for the string abc all valid strings will be
                abc
                ab c
                a bc
                a b c
Example 1:
Input:
str = abc
Output: abc$ab c$a bc$a b c$
Example 2:
Input:
str = xy
Output: xy$x y$
Your Task:
Complete the function spaceString() which takes a character array as an input parameter and returns list of all possible answers in lexographically reverse order(largest String first then smaller). The driver code will print the all possible answer '$' separated.
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(N)
Constraints:
1<= length of string str <=10
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: EASY
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(N)

Starter code:
#Your task is to complete this function

#Function should print the required string

def spaceString(str):

    # Code here

Solutions:
def hp(p, s, a):
	if len(s) == 0:
		a.append(p)
		return
	ch = s[0]
	hp(p + ' ' + ch, s[1:], a)
	hp(p + ch, s[1:], a)

def spaceString(s):
	a = []
	s = ''.join(s)
	pp = s[0]
	hp(pp, s[1:], a)
	return a[::-1]


import sys

def util(a, arr, string, i, j, n):
	if i == n:
		a.append(string)
		return ()
	string += arr[i]
	util(a, arr, string, i + 1, j + 1, n)
	string = string[0:j] + ' '
	string += arr[i]
	util(a, arr, string, i + 1, j + 2, n)

def spaceString(arr):
	string = ''
	string += arr[0]
	a = []
	util(a, arr, string, 1, 1, len(arr))
	return a


import sys
sys.setrecursionlimit(1000000000)

def spaceString(string):
	if len(string) == 0:
		return []
	if len(string) == 1:
		return [string]
	output = list()
	smallOutput = spaceString(string[1:])
	for smallString in smallOutput:
		output.append(string[0] + smallString)
		output.append(string[0] + ' ' + smallString)
	output.sort()
	return output[::-1]


def spaceString(str):
	ans = []
	s = ''.join(str)
	p = s[0]
	helper(p, s[1:], ans)
	return ans[::-1]

def helper(p, s, ans):
	if len(s) == 0:
		ans.append(p)
		return
	ch = s[0]
	helper(p + ' ' + ch, s[1:], ans)
	helper(p + ch, s[1:], ans)


def func(a, temp, ans):
	if not a:
		if temp[0] != ' ':
			ans.append(temp[:])
		return
	func(a[1:], temp + a[0], ans)
	func(a[1:], temp + ' ' + a[0], ans)

def spaceString(a):
	ans = []
	func(a, '', ans)
	return ans


def genStrings(i, res, ans, s):
	if i == len(s) - 1:
		res += s[i]
		ans.append(res)
		return
	genStrings(i + 1, res + s[i] + ' ', ans, s)
	genStrings(i + 1, res + s[i], ans, s)

def spaceString(s):
	ans = []
	res = ''
	genStrings(0, res, ans, s)
	return ans[::-1]


def spaceString(str):

	def backtrack(index, current_str):
		if index == len(str):
			result.append(current_str)
			return
		backtrack(index + 1, current_str + str[index])
		if index < len(str) - 1:
			backtrack(index + 1, current_str + str[index] + ' ')
	result = []
	backtrack(0, '')
	return sorted(result, reverse=True)


def spaceString(s):

	def concatenate(l1, l2):
		l = []
		for i in range(len(l1)):
			for j in range(len(l2)):
				string = l1[i] + l2[j]
				l.append(string)
		return l
	finalStr = [s]
	if len(s) == 1:
		stringList = [s[0]]
		return finalStr
	if len(s) == 2:
		spacedStr = s[0] + ' ' + s[1]
		finalStr.append(spacedStr)
		return finalStr
	for i in range(len(s) - 1):
		spacedStr1 = concatenate(spaceString(s[:i + 1]), spaceString(s[i + 1:]))
		for j in range(len(spacedStr1)):
			finalStr.append(spacedStr1[j])
	allSpaced = ''
	for i in range(len(s)):
		allSpaced = allSpaced + s[i] + ' '
	finalStr.append(allSpaced[:-1])
	return sorted(list(set(finalStr)))[::-1]


def rec(p, s, li):
	if len(s) == 0:
		li.append(p)
		return
	rec(p + ' ' + s[0], s[1:], li)
	rec(p + s[0], s[1:], li)

def spaceString(str):
	li = []
	p = str[0]
	rec(p, str[1:], li)
	return li[::-1]


def helper(S, out, n, res):
	if n == 0:
		res.append(out)
		return
	if n > 1:
		helper(S[1:], out + S[0] + ' ', n - 1, res)
	return helper(S[1:], out + S[0], n - 1, res)

def spaceString(S):
	res = []
	helper(S, '', len(S), res)
	res = res[::-1]
	return res


def helper(s, es, len1, res):
	if len1 == 0:
		res.append(es[:])
		return
	if len1 > 1:
		helper(s[1:], es + s[0] + ' ', len1 - 1, res)
	helper(s[1:], es + s[0], len1 - 1, res)

def spaceString(str):
	S = ''
	S += str
	res = []
	helper(S, '', len(S), res)
	res.sort()
	res = res[::-1]
	return res


def rec(S, i, s):
	if i == len(S):
		return [s]
	res = []
	res.extend(rec(S, i + 1, s + S[i]))
	if i != 0:
		res.extend(rec(S, i + 1, s + ' ' + S[i]))
	return res

def spaceString(str):
	return rec(str, 0, '')


def spaceString(str):
	op = ''
	op += str[0]
	ip = str[1:]
	res = []
	helper(ip, op, res)
	return res

def helper(ip, op, res):
	if len(ip) == 0:
		res.append(op)
		return
	helper(ip[1:], op + ip[0], res)
	helper(ip[1:], op + ' ' + ip[0], res)
	return


def findAllString(res, str, n):
	if len(str) > 2 * n:
		return res
	for i in range(1, len(str)):
		if str[i - 1] == ' ' or str[i] == ' ':
			continue
		else:
			new_string = str[0:i] + ' ' + str[i:]
			new_string = new_string.strip()
			if new_string not in res:
				res.append(new_string)
				res = findAllString(res, new_string, n)
	return res

def spaceString(str):
	res = findAllString([str], str, len(str))
	res.sort(reverse=True)
	return res


def helper(str, i, op, res):
	if i == len(str) - 1:
		op.append(str[i])
		temp = ''.join(op)
		res.append(temp)
		return
	helper(str, i + 1, op + [str[i]], res)
	helper(str, i + 1, op + [str[i], ' '], res)

def spaceString(str):
	res = []
	helper(str, 0, [], res)
	return res


def spaceString(str):

	def fun(output, input, i, n):
		if len(str) == 1:
			return str
		elif n == len(str) - 1:
			l.append(output)
			return
		output1 = output + ' ' + input[i]
		output2 = output + input[i]
		fun(output1, input[i + 1:], i, n + 1)
		fun(output2, input[i + 1:], i, n + 1)
		return l[::-1]
	output = str[0]
	inputi = str[1:]
	i = 0
	n = 0
	l = []
	return fun(output, inputi, i, n)


def fun(ans, arr, string, i, j, n):
	if i == n:
		ans.append(string)
		return
	string += arr[i]
	fun(ans, arr, string, i + 1, j + 1, n)
	string = string[0:j] + ' '
	string += arr[i]
	fun(ans, arr, string, i + 1, j + 2, n)

def spaceString(str):
	ans = []
	string = ''
	string += arr[0]
	fun(ans, str, string, 1, 1, len(str))
	return ans


def ser(S, st, ind, n, A):
	if ind >= n:
		A.append(st)
		return
	ser(S, st + S[ind], ind + 1, n, A)
	ser(S, st + ' ' + S[ind], ind + 1, n, A)

def spaceString(str):
	n = len(str)
	A = []
	ind = 1
	st = str[0]
	ser(str, st, ind, n, A)
	return A


def spaceString(s):
	return sorted(helper([s], len(s) - 1), reverse=True)

def helper(arr, i):
	if i == 0:
		return arr
	temp = [item[:i] + ' ' + item[i:] for item in arr]
	return helper(arr + temp, i - 1)


def spaceString(str):
	strs = []
	if len(str) == 1:
		strs.append(str)
		return strs
	strsTemp = spaceString(str[:len(str) - 1])
	for i in range(len(strsTemp)):
		strs.append(strsTemp[i] + str[-1])
		strs.append(strsTemp[i] + ' ' + str[-1])
	return strs


def spaceString(s):
	ans = []
	s += '0'
	temp = '' + s[0]
	i = 1
	strin(s, temp, ans, i)
	return ans

def strin(s, temp, ans, i):
	if s[i] == '0':
		ans.append(temp)
		return
	strin(s, temp + s[i], ans, i + 1)
	strin(s, temp + ' ' + s[i], ans, i + 1)


def spaceString(str):
	s1 = str[0]
	s2 = str[1:]
	l = []
	helper(s1, s2, l)
	return l

def helper(s1, s2, l):
	if len(s2) == 0:
		l.append(s1)
		return
	helper(s1 + s2[0], s2[1:], l)
	helper(s1 + ' ' + s2[0], s2[1:], l)
	return l


def spaceString(stri):
	newstr = stri[0]
	store = []
	helper(stri, 0, len(stri), newstr, store)
	return store

def helper(stri, p, n, newstring, ans):
	if p == n - 1:
		ans.append(newstring)
		return
	helper(stri, p + 1, n, newstring + stri[p + 1], ans)
	helper(stri, p + 1, n, newstring + ' ' + stri[p + 1], ans)


def spaceString(s):
	ans = []

	def f(i, s, temp):
		if i == len(s):
			ans.append(temp)
			return
		f(i + 1, s, temp + s[i])
		f(i + 1, s, temp + ' ' + s[i])
	temp = s[0]
	f(1, s, temp)
	return ans


def spaceString(str):

	def solve(str, i):
		s.add(str)
		if i == len(str):
			return
		for j in range(i + 1, len(str)):
			str1 = str[:j]
			str1 += ' '
			str1 += str[j:]
			solve(str1, j + 1)
			solve(str, j + 1)
	s = set()
	solve(str, 0)
	s = list(s)
	s.sort()
	return s[::-1]


def spaceString(str):
	arr = []

	def rec(ind, st):
		if ind >= len(str):
			arr.append(st)
			return
		if st[-1] == ' ':
			rec(ind + 1, st + str[ind])
		else:
			rec(ind + 1, st + str[ind])
			rec(ind, st + ' ')
		return
	rec(1, str[0])
	return arr


def helper(str, index, res, ans):
	if index == len(str) - 1:
		ans += str[index]
		res.append(ans)
		return
	helper(str, index + 1, res, ans + str[index])
	helper(str, index + 1, res, ans + str[index] + ' ')

def spaceString(str):
	index = 0
	res = []
	ans = ''
	helper(str, index, res, ans)
	return res


ans = []

def addSpace(str, ind):
	if ind <= 0:
		ans.append(str)
	else:
		addSpace(str[:ind] + '' + str[ind:], ind - 1)
		addSpace(str[:ind] + ' ' + str[ind:], ind - 1)

def spaceString(str):
	global ans
	ans = []
	addSpace(str, len(str) - 1)
	ans.sort()
	ans = ans[::-1]
	return ans


def spaceString(strg):

	def helper(p, s, ans):
		if len(s) == 0:
			ans.append(p)
			return
		ch = s[0]
		helper(p + ' ' + ch, s[1:], ans)
		helper(p + ch, s[1:], ans)
	ans = []
	s = strg
	p = s[0]
	helper(p, s[1:], ans)
	return ans[::-1]


def spaceString(str):
	n = len(str)
	num_spaces = n - 1
	ans = []

	def select(x, s, r):
		if x == num_spaces:
			ans.append(s)
			return
		select(x + 1, s, r)
		select(x + 1, s[0:x + 1 + r] + ' ' + s[x + 1 + r:], r + 1)
	select(0, str, 0)
	return ans


def spaceString(str):
	ans = []

	def help(str, index=0, final=''):
		final += str[index]
		if index == len(str) - 1:
			ans.append(final)
			return
		help(str, index + 1, final)
		final += ' '
		help(str, index + 1, final)
	help(str)
	return ans


def spaceString(stri):
	ans = util(stri)
	ans.sort(reverse=True)
	return ans

def util(stri):
	strs = []
	if len(stri) == 1:
		strs.append(stri)
		return strs
	strTemp = util(stri[1:])
	for i in range(len(strTemp)):
		strs.append(stri[0] + strTemp[i])
		strs.append(stri[0] + ' ' + strTemp[i])
	return strs


def reqSpaces(str):
	if len(str) == 1:
		return [str]
	else:
		resp = reqSpaces(str[1:])
		lisone = [str[0] + x for x in resp]
		listwo = [str[0] + ' ' + x for x in resp]
		lisone.extend(listwo)
		return lisone

def spaceString(str):
	val = reqSpaces(str)
	return val


def spaceString(s):
	res = []
	op = ''

	def solve(s, op):
		if len(s) == 0:
			res.append(op)
			return
		op1 = op[:] + s[0]
		op2 = op[:] + ' ' + s[0]
		solve(s[1:], op1)
		solve(s[1:], op2)
	solve(s[1:], s[0])
	return res


def spaceString(str):

	def helper(i, st):
		if i == len(str) - 1:
			ans.append(st + str[-1])
			return
		helper(i + 1, st + str[i])
		helper(i + 1, st + str[i] + ' ')
	ans = []
	helper(0, '')
	return ans


def spaceString(str):

	def fun(res, n, s, ans):
		if n == len(s):
			res.append(ans)
			return
		fun(res, n + 1, s, ans + s[n])
		fun(res, n + 1, s, ans + ' ' + s[n])
	res = []
	s = [*str]
	n = 1
	ans = s[0]
	fun(res, n, s, ans)
	return res


def spaceString(str):
	resultantString = []
	if len(str) == 1:
		resultantString.append(str)
		return resultantString
	stringTemp = spaceString(str[1:])
	for i in range(len(stringTemp)):
		resultantString.append(str[0] + stringTemp[i])
		resultantString.append(str[0] + ' ' + stringTemp[i])
	resultantString.sort()
	return resultantString[::-1]


def spaceString(S):
	lis = []
	if len(S) == 0:
		return lis
	if len(S) == 1:
		lis.append(S)
		return lis
	tempstr = spaceString(S[1:])
	for x in range(len(tempstr)):
		lis.append(S[0] + tempstr[x])
		lis.append(S[0] + ' ' + tempstr[x])
	lis.sort()
	return lis[::-1]


def spaceString(str):

	def getSubStrings(index, temp, str):
		if index == len(str):
			result.append(temp)
			return
		temp = temp + str[index]
		getSubStrings(index + 1, temp, str)
		temp = temp[:-1]
		temp = temp + ' ' + str[index]
		getSubStrings(index + 1, temp, str)
		temp = temp[:-2]
	result = []
	str = list(str)
	getSubStrings(1, str[0], str)
	return result


def spaceString(str):
	output = []

	def recur(string, sol):
		if len(string) == 0:
			output.append(sol)
			return
		first = string[0]
		recur(string[1:], sol + first)
		if len(sol) != 0:
			recur(string[1:], sol + ' ' + first)
	recur(str, '')
	return output


def getSpaces(str1, str2, wordsWithSpaces):
	if not len(str2):
		wordsWithSpaces.append(str1)
		return
	currentChar = str2[:1]
	getSpaces(str1 + currentChar, str2[1:], wordsWithSpaces)
	getSpaces(str1 + ' ' + currentChar, str2[1:], wordsWithSpaces)

def spaceString(str):
	wordsWithSpaces = []
	(completedString, uncompletedString) = (str[0], str[1:])
	getSpaces(completedString, uncompletedString, wordsWithSpaces)
	return wordsWithSpaces


def spaceString(string):
	n = len(string)
	mylist = []
	if n == 1:
		mylist.append(string)
		return mylist
	tempstring = spaceString(string[:n - 1])
	for i in range(len(tempstring)):
		mylist.append(tempstring[i] + string[n - 1])
		mylist.append(tempstring[i] + ' ' + string[n - 1])
	return mylist


def spaceString(str):

	def rec(s):
		if len(s) == 1:
			return [s]
		res = []
		for ss in rec(s[1:]):
			res.append(s[0] + ss)
			res.append(s[0] + ' ' + ss)
		return res
	return reversed(sorted(rec(str)))


def spaceString(str):
	if len(str) == 1:
		return [str]
	ans = []
	p = spaceString(str[:-1])
	choices = ['', ' ']
	for c in p:
		for choice in choices:
			ans.append(c + choice + str[-1])
	return ans


def spaceString(str):
	lst = []
	if len(str) == 1:
		lst.append(str)
		return lst
	temp = spaceString(str[1:])
	for i in range(len(temp)):
		lst.append(str[0] + temp[i])
		lst.append(str[0] + ' ' + temp[i])
	return sorted(lst, reverse=True)


def perm(c, t, n, st, l):
	if c == n - 1:
		t += st[n - 1]
		l.append(t)
		return
	t1 = t + st[c]
	t2 = t + st[c] + ' '
	perm(c + 1, t1, n, st, l)
	perm(c + 1, t2, n, st, l)

def spaceString(st):
	l = []
	perm(0, '', len(st), st, l)
	l.sort()
	l = l[::-1]
	return l


def spaceString(_str):
	ans = []
	possibleString(_str, 0, ans, '')
	return ans

def possibleString(_str, index, ans, tempStr):
	if len(_str) == index:
		ans.append(tempStr)
		return
	c = _str[index]
	if index == 0:
		possibleString(_str, index + 1, ans, tempStr + c)
	else:
		possibleString(_str, index + 1, ans, tempStr + c)
		possibleString(_str, index + 1, ans, tempStr + ' ' + c)


def itr(n, ip, op, l):
	if len(op) == 0:
		l.append(ip)
		return
	if len(op) == n:
		itr(n, ip + op[0], op[1:], l)
	else:
		itr(n, ip + ' ' + op[0], op[1:], l)
		itr(n, ip + op[0], op[1:], l)

def spaceString(str):
	n = len(str)
	l = []
	itr(n, '', str, l)
	l = l[::-1]
	return l


def spaceString(str):
	res = []
	if len(str) == 1:
		res.append(str)
		return str
	ch = str[0]
	strs = spaceString(str[1:])
	for i in range(len(strs)):
		res.append(ch + strs[i])
		res.append(ch + ' ' + strs[i])
	res.sort(reverse=True)
	return res


def spaceString(str):
	input = str
	output = input[0]
	li = []
	solve(input[1:], output, li)
	li = li[::-1]
	return li

def solve(input, output, li):
	if len(input) == 0:
		li.append(output)
		return
	solve(input[1:], output + ' ' + input[0], li)
	solve(input[1:], output + input[0], li)


def spaceString(str):
	n = len(str)
	p = 2 ** n
	newstr = str[0]
	store = []
	helper(str, 0, len(str), newstr, store)
	return store

def helper(str, p, n, newstring, ans):
	if p == n - 1:
		ans.append(newstring)
		return
	helper(str, p + 1, n, newstring + str[p + 1], ans)
	helper(str, p + 1, n, newstring + ' ' + str[p + 1], ans)


def spaceString(strs):
	arr = []

	def solve(i, st):
		nonlocal arr
		if i == len(strs) - 1:
			st += strs[i]
			arr.append(st)
			return
		solve(i + 1, st + strs[i])
		solve(i + 1, st + strs[i] + ' ')
	solve(0, '')
	return arr


def spaceString(str):
	strs = []
	if len(str) == 1:
		strs.append(str)
		return strs
	temp = spaceString(str[1:])
	for i in range(len(temp)):
		strs.append(str[0] + temp[i])
		strs.append(str[0] + ' ' + temp[i])
	strs.sort()
	strs.reverse()
	return strs


def spaceString(str):

	def makeIt(str):
		c = []
		if len(str) == 0:
			return []
		if len(str) == 1:
			c.append(str)
			return c
		for perm in makeIt(str[1:]):
			c.append(str[0] + ' ' + perm)
			c.append(str[0] + perm)
		return c
	collection = makeIt(str)
	collection.sort()
	collection.reverse()
	return collection


def spaceString(str):

	def space(str, s, i, a):
		i = i + 1
		if i == len(str):
			a.append(s)
			return
		space(str, s + ' ' + str[i], i, a)
		space(str, s + str[i], i, a)
		return
	s = str[0]
	i = 0
	a = []
	space(str, s, i, a)
	return a[::-1]


def spaceString(str):
	if len(str) == 1:
		return str
	ans = []

	def solve(str, i, res):
		if i == len(str):
			res = res.strip()
			if res not in ans:
				ans.append(res)
			return
		solve(str, i + 1, res)
		if i != 0 or i != len(str) - 1:
			res = res[:i + 1] + ' ' + res[i + 1:]
		solve(res, i + 2, res)
		return ans
	solve(str, 0, str)
	return ans


def spaceString(s):
	n = len(s)
	l = []

	def solve(a, b, x):
		if x == 0:
			l.append(''.join(b))
			return
		for i in range(x):
			b.append(' '.join(a[:i + 1]))
			solve(a[i + 1:], b, x - (i + 1))
			b.pop(-1)
	solve([i for i in s], [], n)
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip()
		a = spaceString(arr)
		for _ in a:
			print(_, end='$')
		print()


def spaceString(str):
	arr = []
	recgen('', 0, str, arr)
	return arr

def recgen(s, i, S, arr):
	if len(S) == i:
		arr.append(s)
		return
	if i < len(S):
		recgen(s + S[i], i + 1, S, arr)
	if i != 0:
		recgen(s + ' ' + S[i], i + 1, S, arr)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip()
		a = spaceString(arr)
		for _ in a:
			print(_, end='$')
		print()


def spaceString(stri):
	newstr = stri[0]
	store = []
	helper(stri, 0, len(stri), newstr, store)
	return store

def helper(stri, p, n, newstring, ans):
	if p == n - 1:
		ans.append(newstring)
		return
	helper(stri, p + 1, n, newstring + stri[p + 1], ans)
	helper(stri, p + 1, n, newstring + ' ' + stri[p + 1], ans)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip()
		a = spaceString(arr)
		for _ in a:
			print(_, end='$')
		print()


def spaceString(str):
	a = []
	if len(str) == 1:
		a.append(str)
		return a
	else:
		for i in spaceString(str[1:]):
			a.append(str[0] + ' ' + i)
			a.append(str[0] + i)
		a.sort()
		return a[::-1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		arr = input().strip()
		a = spaceString(arr)
		for _ in a:
			print(_, end='$')
		print()


def spaceString(str):
	arr = []

	def solve(i, out, arr):
		if i == len(str) - 1:
			out += str[i]
			arr.append(out)
			return
		exclude = solve(i + 1, out + str[i], arr)
		include = solve(i + 1, out + str[i] + ' ', arr)
	solve(0, '', arr)
	return arr


def spaceString(stri):
	a = []

	def space(p, stri):
		if len(stri) == 1:
			a.append(p + stri[0])
			return
		ch = stri[0]
		space(p + ch, stri[1:])
		space(p + ch + ' ', stri[1:])
	space('', stri)
	return a


def spaceString(S):
	ans = solver(S)
	return sorted(ans, reverse=True)

def solver(s):
	if len(s) == 1:
		return [s]
	temp = s[0]
	ros = s[1:]
	res = solver(ros)
	ans = []
	for el in res:
		ans.append(temp + el)
		ans.append(temp + ' ' + el)
	return ans


def spaceString(S):
	n = len(S)
	if n == 0:
		return []
	if n == 1:
		return [S]
	curr = S[0]
	res = spaceString(S[1:])
	ws = [curr + ' ' + x for x in res]
	wos = [curr + x for x in res]
	return wos + ws


def spaceString(str):

	def posstr(strs):
		st = []
		if len(strs) == 1:
			st.append(strs)
			return st
		stemp = posstr(strs[1:])
		for i in range(len(stemp)):
			st.append(strs[0] + stemp[i])
			st.append(strs[0] + ' ' + stemp[i])
		return st
	return list(sorted(posstr(str), reverse=True))


def spaceString(str):
	n = len(str)

	def fun(str, l):
		if l == 1:
			return [str]
		else:
			res = fun(str[1:], l - 1)
			return [str[0] + r for r in res] + [str[0] + ' ' + r for r in res]
	return fun(str, n)


def spaceString(str):

	def rec(res, s, str, i):
		if i == len(str) - 1:
			s += str[i]
			res.append(s)
			return
		rec(res, s + str[i] + ' ', str, i + 1)
		rec(res, s + str[i], str, i + 1)
	res = []
	s = ''
	rec(res, s, str, 0)
	res.sort(reverse=True)
	return res


def spaceString(str):
	lis = []
	op = str[0]
	str = str[1:]
	solve(str, op, lis)
	lis.sort(reverse=True)
	return lis

def solve(str, op, lis):
	if len(str) == 0:
		lis.append(op)
		return
	op1 = op
	op2 = op
	op1 += ' '
	op1 += str[0]
	op2 += str[0]
	str = str[1:]
	solve(str, op1, lis)
	solve(str, op2, lis)