Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. The output should be printed in sorted increasing order of strings
Example 1:
Input:
S = "ABC"
Output: (A B C)(A BC)(AB C)(ABC)
Explanation:
ABC
AB C
A BC
A B C
These are the possible combination of "ABC".
 
Example 2:
Input:
S = "AB"
Output: (A B)(AB)
Your Task:  
You don't need to read input or print anything. Your task is to complete the function permutation() which takes the string S as input parameters and returns the sorted array of the string denoting the different permutation (DON'T ADD '(' and ')' it will be handled by the driver code only).
Expected Time Complexity: O(2^n)
Expected Auxiliary Space: O(1)
 
CONSTRAINTS:
1 <= |S| < 10
S only contains lowercase and Uppercase English letters.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(2^n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def permutation (self, S):

        # code here

        pass





Solutions:
class Solution:

	def permutation(self, S):
		ip = S[1:]
		op = S[0]
		ans = []

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


class Solution:

	def permutation(self, S):
		op = S[0]
		result = []
		S = S[1:]
		self.subsetswithspaces(S, op, result)
		result.sort()
		return result

	def subsetswithspaces(self, ip, op, result):
		if not ip:
			result.append(op)
			return
		op1 = op + ip[0]
		op2 = op + ' ' + ip[0]
		ip = ip[1:]
		self.subsetswithspaces(ip, op1, result)
		self.subsetswithspaces(ip, op2, result)


class Solution:

	def permutation(self, S):
		if len(S) <= 1:
			return [S]
		answer = []
		ip = S[1:]
		op = S[0]
		self.solve(ip, op, answer)
		return answer

	def solve(self, ip, op, answer):
		if len(ip) == 0:
			answer.append(op + ip)
			return
		else:
			op1 = op + ' ' + ip[0]
			op2 = op + ip[0]
			ip = self.erase(ip)
			self.solve(ip, op1, answer)
			self.solve(ip, op2, answer)
			return

	def erase(self, ip):
		if len(ip) <= 1:
			return ''
		else:
			return ip[1:]


class Solution:

	def permutation(self, S):
		ans = []
		new = []
		n = len(S)

		def solve(ind, new, S, ans):
			if ind == n:
				ans.append(''.join(new))
				return
			if ind == 0:
				new.append(S[ind])
				solve(ind + 1, new, S, ans)
			else:
				new.append(' ')
				new.append(S[ind])
				solve(ind + 1, new, S, ans)
				new.pop()
				new.pop()
				new.append(S[ind])
				solve(ind + 1, new, S, ans)
				new.pop()
		solve(0, new, S, ans)
		return ans


class Solution:

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


class Solution:

	def permutation(self, S):

		def permute(string):
			list1 = []
			if len(string) == 1:
				list1.append(string)
				return list1
			strspaced = permute(string[1:])
			for i in range(len(strspaced)):
				list1.append(string[0] + strspaced[i])
				list1.append(string[0] + ' ' + strspaced[i])
			return list1
		return sorted(permute(S))


class Solution:

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

	def permutation(self, S):
		n = len(S)
		l = []
		self.solve(n, '', S, l)
		return l


class Solution:

	def permutation(self, s):
		l = len(s)
		res = []

		def solve(ind, stri):
			if ind == l - 1:
				stri += s[ind]
				res.append(stri)
				return
			a = stri + s[ind]
			b = stri + s[ind] + ' '
			solve(ind + 1, a)
			solve(ind + 1, b)
		solve(0, '')
		res.sort()
		return res


class Solution:

	def permutation(self, S):
		res = []

		def fun(S, i, ans):
			if len(S) == i:
				res.append(ans)
			elif i == 0:
				fun(S, i + 1, ans + S[i])
			else:
				fun(S, i + 1, ans + ' ' + S[i])
				fun(S, i + 1, ans + S[i])
		fun(S, 0, '')
		return res


class Solution:

	def permutation(self, S):

		def calc(s, temp):
			if len(s) == 0:
				app = ' '.join(temp)
				if app not in ans:
					ans.append(app)
				return
			for i in range(len(S)):
				temp.append(s[:i + 1])
				calc(s[i + 1:], temp)
				temp.pop()
		ans = []
		calc(S, [])
		return ans


class Solution:

	def solve(self, op, ip, ans):
		if len(ip) == 0:
			ans.append(op)
			return
		ch = ip[0]
		self.solve(op + ' ' + ch, ip[1:], ans)
		self.solve(op + ch, ip[1:], ans)

	def permutation(self, S):
		ans = []
		ip = S
		op = ip[0]
		self.solve(op, ip[1:], ans)
		return ans


class Solution:

	def permutation(self, S):
		ans = []

		def recur(S, i, cur, ans):
			if i == len(S):
				ans.append(cur[:])
				return
			cur += ' ' + S[i]
			recur(S, i + 1, cur, ans)
			cur = cur[:len(cur) - 2] + S[i]
			recur(S, i + 1, cur, ans)
			return
		recur(S, 1, S[0], ans)
		return ans


class Solution:

	def permutation(self, S):

		def helper(s, ind, cur, res):
			if ind == len(s):
				res.append(cur)
				return
			helper(s, ind + 1, cur + ' ' + s[ind], res)
			helper(s, ind + 1, cur + s[ind], res)
		res = []
		cur = S[0]
		helper(S, 1, cur, res)
		res.sort()
		return res


class Solution:

	def permutation(self, S):
		self.n = len(S)
		return self._permute(0, S, '', [])

	def _permute(self, i, S, per, ans):
		if i == self.n - 1:
			per += S[i]
			ans.append(per)
			return ans
		ans = self._permute(i + 1, S, per + S[i] + ' ', ans)
		ans = self._permute(i + 1, S, per + S[i], ans)
		return ans


class Solution:

	def permutation(self, S):

		def recurs(i, vals):
			nonlocal res
			if i >= len(S):
				if len(vals) >= len(S):
					vals.pop()
					res.append(''.join(vals.copy()))
				return
			recurs(i + 1, vals + [S[i]] + [' '])
			recurs(i + 1, vals + [S[i]])
		res = []
		recurs(0, [])
		sorted(res)
		check = len(S)
		result = []
		for i in res:
			sums = 0
			for j in i:
				if j.isalpha():
					sums += 1
			if sums == check:
				result.append(i)
		return result


class Solution:

	def findAll(self, i, s1, ans, S):
		if i == len(S) - 1:
			s1 += S[i]
			ans.append(s1)
			return
		self.findAll(i + 1, s1 + S[i] + ' ', ans, S)
		self.findAll(i + 1, s1 + S[i], ans, S)

	def permutation(self, S):
		ans = []
		s1 = ''
		self.findAll(0, s1, ans, S)
		return ans


class Solution:

	def per(self, s, idx, ans):
		if idx == len(s) - 1:
			ans.append(s)
			return
		self.per(s[0:idx + 1] + ' ' + s[idx + 1:], idx + 2, ans)
		self.per(s, idx + 1, ans)

	def permutation(self, S):
		ans = []
		self.per(S, 0, ans)
		return ans


class Solution:

	def permutation(self, s):
		res = []

		def rec(ind, cur_str):
			if ind == len(s):
				res.append(cur_str)
				return
			if ind == 0:
				rec(ind + 1, cur_str + s[ind])
			else:
				rec(ind + 1, cur_str + ' ' + s[ind])
				rec(ind + 1, cur_str + s[ind])
		rec(0, '')
		return res


class Solution:

	def permutation(self, S):

		def solve(per, s):
			ans = []
			if not s:
				ans.append(per)
				return ans
			ans += solve(per + ' ' + s[0], s[1:])
			ans += solve(per + s[0], s[1:])
			return ans
		per = S[0]
		return solve(per, S[1:])


class Solution:

	def permutation(self, S):
		n = len(S)

		def rec(i, n, S, curr, res):
			if i == n:
				res.append(curr)
				return
			curr += S[i]
			rec(i + 1, n, S, curr, res)
			curr = curr[:-1]
			curr += ' ' + S[i]
			rec(i + 1, n, S, curr, res)
		res = []
		curr = S[0]
		rec(1, n, S, curr, res)
		res.sort()
		return res


class Solution:

	def permutation(self, S):

		def solve(ip, op, result):
			if len(ip) == 0:
				result.append(op)
				return
			op1 = op
			op1 += ip[0]
			op2 = op
			op2 += ' '
			op2 += ip[0]
			ip = ip[1:]
			solve(ip, op2, result)
			solve(ip, op1, result)
		ot = S[0]
		S = S[1:]
		result = []
		solve(S, ot, result)
		return result


class Solution:

	def solve(self, i, s, li, a):
		if i == len(s):
			if a:
				if a[-1] != ' ':
					li.append(a)
			return
		a += s[i]
		if i < len(s):
			a += ' '
		self.solve(i + 1, s, li, a)
		a = a[:-1]
		self.solve(i + 1, s, li, a)

	def permutation(self, S):
		li = []
		self.solve(0, S, li, '')
		return li


class Solution:

	def permutation(self, 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:
			return finalStr
		if len(s) == 2:
			spacedStr = s[0] + ' ' + s[1]
			finalStr.append(spacedStr)
			return finalStr[::-1]
		for i in range(len(s) - 1):
			spacedStr1 = concatenate(self.permutation(s[:i + 1]), self.permutation(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)))


class Solution:

	def permutation(self, S):
		arr = []
		st = ''
		self.traverse(S, arr, st, 0)
		arr.sort()
		return arr

	def traverse(self, s, arr, st, i):
		if i == len(s):
			arr.append(st)
			return
		st += s[i]
		self.traverse(s, arr, st, i + 1)
		if i + 1 < len(s):
			st += ' '
			self.traverse(s, arr, st, i + 1)


class Solution:

	def permutation(self, S):

		def sorted_per(i, s, S, res, n):
			if i == n:
				res.append(s)
				return
			n_s = s
			y_s = s
			n_s += S[i]
			y_s += ' '
			y_s += S[i]
			sorted_per(i + 1, n_s, S, res, n)
			sorted_per(i + 1, y_s, S, res, n)
		n = len(S)
		res = []
		s = S[0]
		sorted_per(1, s, S, res, n)
		res.sort()
		return res


class Solution:

	def permutation(self, S):
		inp = S
		out = ''
		out = out + inp[0]
		inp = inp[1:]
		ans = []

		def solve(inp, out, ans):
			if len(inp) == 0:
				ans.append(out)
				return
			out1 = out
			out2 = out
			out2 += inp[0]
			out1 += ' ' + inp[0]
			inp = inp[1:]
			solve(inp, out1, ans)
			solve(inp, out2, ans)
			return
		solve(inp, out, ans)
		return ans


def possible_ways(ind, stri, res, S):
	if ind == len(S) - 1:
		stri += S[ind]
		res.append(stri)
		return
	possible_ways(ind + 1, stri + S[ind] + ' ', res, S)
	possible_ways(ind + 1, stri + S[ind], res, S)

class Solution:

	def permutation(self, S):
		stri = ''
		res = []
		possible_ways(0, stri, res, S)
		return res


class Solution:

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

	def permutation(self, S):
		res = []
		self.helper(S, '', len(S), res)
		return res


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

class Solution:

	def permutation(self, S):
		return rec(S, '', 0)


class Solution:

	def permutation(self, S):
		res = []

		def helper(curr, idx):
			if idx == len(S):
				res.append(curr)
				return
			helper(curr + S[idx], idx + 1)
			if idx < len(S) - 1:
				helper(curr + S[idx] + ' ', idx + 1)
		helper('', 0)
		return sorted(res)


class Solution:

	def permutation(self, s):
		ans = []

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


class Solution:

	def permutation(self, S):
		ans = []

		def fun(ip, op):
			if len(ip) == 0:
				ans.append(op)
				return
			op1 = op + ip[0]
			op2 = op + ' ' + ip[0]
			fun(ip[1:], op1)
			fun(ip[1:], op2)
		fun(S[1:], S[0])
		ans.sort()
		return ans


class Solution:

	def permutation(self, S):
		self.res = []
		op = ''
		op += S[0]
		self.helper(S[1:], op)
		return sorted(self.res)

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


class Solution:

	def permutation(self, S):

		def spaces(ip, op, a):
			if len(ip) == 0:
				a.append(op)
				return
			op1 = op + ' ' + ip[0]
			op2 = op + ip[0]
			ip = ip[1:]
			spaces(ip, op1, a)
			spaces(ip, op2, a)
		a = []
		spaces(S[1:], S[0], a)
		return a


class Solution:

	def permutation(self, S):
		pass
		output = []

		def recurPlace(index, currString):
			if index == len(S) - 1:
				temp = currString + S[len(S) - 1]
				output.append(temp)
				return
			place = recurPlace(index + 1, currString + S[index] + ' ')
			noPlace = recurPlace(index + 1, currString + S[index])
		recurPlace(0, '')
		return sorted(output)


class Solution:
	solution = []

	def subSets(self, ip, op):
		if len(op) == 0:
			self.solution.append(ip)
			return
		self.subSets(ip + ' ' + op[0], op[1:])
		self.subSets(ip + op[0], op[1:])

	def permutation(self, S):
		self.solution.clear()
		self.subSets(S[0], S[1:])
		return self.solution


class Solution:

	def permutation(self, S):
		if not S:
			return ''
		if len(S) == 1:
			return S[0]
		res = []
		temp = ['']

		def getPermutation(S):
			if len(S) == 2:
				temp[0] += S[0] + ' ' + S[1]
				res.append(temp[0])
				temp[0] = temp[0][:-3]
				temp[0] += S
				res.append(temp[0])
				temp[0] = temp[0][:-2]
			else:
				temp[0] += S[0] + ' '
				getPermutation(S[1:])
				temp[0] = temp[0][:-1]
				getPermutation(S[1:])
				temp[0] = temp[0][:-1]
		getPermutation(S)
		return res


class Solution:

	def permutation(self, S):

		def determineStrings(ans, op, ip):
			if len(ip) == 1:
				op.append(ip)
				ans.append(''.join(op))
				return
			(op1, op2) = (op.copy(), op.copy())
			op1.append(ip[0])
			op2.append(ip[0] + ' ')
			determineStrings(ans, op1, ip[1:])
			determineStrings(ans, op2, ip[1:])
		ans = []
		(op, ip) = ([], S)
		determineStrings(ans, op, ip)
		ans.sort()
		return ans


class Solution:

	def permutation(self, S):
		a = []
		self.find(S, a, '', 0)
		a.sort()
		return a

	def find(self, S, a, str1, i):
		if i == len(S):
			a.append(str1)
			return
		else:
			str1 += S[i]
			self.find(S, a, str1, i + 1)
			if i + 1 != len(S):
				str1 += ' '
				self.find(S, a, str1, i + 1)


class Solution:

	def permutation(self, S):
		res = self.func('', [], S, 0)
		return res

	def func(self, string, answer, S, index):
		if index == len(S) - 1:
			string += S[index]
			answer.append(string)
			return answer
		self.func(string + S[index] + ' ', answer, S, index + 1)
		self.func(string + S[index], answer, S, index + 1)
		return answer


class Solution:

	def permutation(self, s):
		input = s[1:]
		output = s[0]
		lst = []

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


class Solution:

	def permutation(self, S):
		op = S[0]
		S = S[1:]
		res = []

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


def Bab(S, str1, ind, A, n):
	if ind >= n - 1:
		m = str1 + S[ind]
		A.append(m)
		return
	m = str1 + S[ind]
	Bab(S, m + ' ', ind + 1, A, n)
	Bab(S, m, ind + 1, A, n)

class Solution:

	def permutation(self, S):
		n = len(S)
		if n == 1:
			return S
		A = []
		Bab(S, S[0] + ' ', 1, A, n)
		Bab(S, S[0], 1, A, n)
		return A


class Solution:

	def permutation(self, S):
		return sorted(self.helper([S], len(S) - 1))

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


class Solution:

	def permutation(self, s):
		ans = []
		s += '0'
		temp = '' + s[0]
		i = 1
		self.strin(s, temp, ans, i)
		return ans[::-1]

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


class Solution:

	def permutation(self, S):
		result = []

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


class Solution:

	def permutation(self, S):
		output = ''
		output += S[0]
		S = S[1:]
		outlist = []

		def perm(S, output):
			if len(S) == 0:
				outlist.append(output)
				return
			out1 = output
			out2 = output
			val = S[0]
			S = S[1:]
			out1 += val
			out2 += ' ' + val
			perm(S, out1)
			perm(S, out2)
		perm(S, output)
		return sorted(outlist)


class Solution:

	def permutation(self, S):
		s1 = S[0]
		s2 = S[1:]
		l = []
		self.helper(s1, s2, l)
		return l

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


class Solution:

	def permutation(self, S):
		output = '' + S[0]
		inputi = S[1:]
		i = 0
		l = []
		if len(S) == 1:
			return S

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


class Solution:

	def permutation(self, S):

		def rec(S, res, index, temp):
			if index == len(S) - 1:
				temp += S[index]
				res.append(temp)
				return
			rec(S, res, index + 1, temp + S[index] + ' ')
			rec(S, res, index + 1, temp + S[index])
		res = []
		index = 0
		temp = ''
		rec(S, res, index, temp)
		return res


class Solution:

	def permutation(self, S):
		res = []
		sub = S[0]

		def solve(i, sub):
			if i >= len(S):
				res.append(sub)
				return
			sub += ' ' + S[i]
			solve(i + 1, sub)
			sub = sub[:-2]
			sub += S[i]
			solve(i + 1, sub)
		solve(1, S[0])
		return res


class Solution:

	def helper(self, p, up, result):
		if len(up) == 1:
			result.append(p + up)
			return
		self.helper(p + up[0] + ' ', up[1:], result)
		self.helper(p + up[0], up[1:], result)

	def permutation(self, S):
		result = []
		self.helper('', S, result)
		return result


class Solution:

	def permutation(self, S):

		def backtrack(curr, idx):
			if idx == len(S) - 1:
				curr.append(S[idx])
				ans.append(''.join(curr.copy()))
				curr.pop()
				return
			curr.append(S[idx])
			curr.append(' ')
			backtrack(curr, idx + 1)
			curr.pop()
			backtrack(curr, idx + 1)
			curr.pop()
		ans = []
		backtrack([], 0)
		return ans


class Solution:

	def permutation(self, S):
		input = S[1:]
		output = S[0]
		ls = []

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


class Solution:

	def slove(S, ans, output, index):
		if index == len(S) - 1:
			output += S[index]
			ans.append(output)
			return
		Solution.slove(S, ans, output + S[index] + ' ', index + 1)
		Solution.slove(S, ans, output + S[index], index + 1)

	def permutation(self, S):
		index = 0
		ans = []
		output = ''
		Solution.slove(S, ans, output, index)
		return ans


a = []

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

class Solution:

	def permutation(self, S):
		global a
		a = []
		addSpace(S, len(S) - 1)
		a.sort()
		return a


class Solution:

	def permutation(self, S):
		if len(S) <= 1:
			return [S]
		res = []
		combinations_of_rest = self.permutation(S[1:])
		for c in combinations_of_rest:
			res.append(S[0] + ' ' + c)
			res.append(S[0] + c)
		return sorted(res)


class Solution:

	def permutation(self, S):

		def sol(i, op):
			if i >= len(S):
				ans.append(op)
				return
			sol(i + 1, op + ' ' + S[i])
			sol(i + 1, op + S[i])
		ans = []
		sol(1, S[0])
		return ans


class Solution:

	def permutation(self, S):
		li = []
		if len(S) == 0:
			return li
		if len(S) == 1:
			li.append(S)
			return li
		string = self.permutation(S[1:])
		for i in range(len(string)):
			li.append(S[0] + string[i])
			li.append(S[0] + ' ' + string[i])
		li.sort()
		return li


class Solution:

	def permutation(self, s):
		op = ''
		ip = s[1:]
		op += s[0]
		c = []

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


class Solution:

	def permutation(self, S):
		n = len(S)
		ans = []
		self.permutationHelper(S, n - 1, ans)
		ans.sort()
		return ans

	def permutationHelper(self, s, i, ans):
		if i == 0:
			ans.append(s)
			return s
		self.permutationHelper(s, i - 1, ans)
		self.permutationHelper(s[0:i] + ' ' + s[i:], i - 1, ans)


class Solution:

	def permutation(self, S):
		n = len(S)
		ans = []
		if n == 1:
			return [S]

		def util(index, op):
			if index == n - 1:
				op = op + S[index]
				ans.append(op)
				return
			util(index + 1, op + S[index])
			util(index + 1, op + S[index] + ' ')
		util(0, '')
		ans.sort()
		return ans


class Solution:

	def helper(self, S, curr, i, ans):
		if i == len(S):
			ans.append(curr)
			return
		self.helper(S, curr + ' ' + S[i], i + 1, ans)
		self.helper(S, curr + S[i], i + 1, ans)
		return

	def permutation(self, S):
		ans = []
		curr = S[0]
		self.helper(S, curr, 1, ans)
		return ans


class Solution:

	def permutation(self, S):
		ans = []
		self.solve(0, '', ans, S)
		return ans

	def solve(self, i, out, ans, S):
		if i == len(S) - 1:
			out += S[i]
			ans.append(out)
			return
		self.solve(i + 1, out + S[i] + ' ', ans, S)
		self.solve(i + 1, out + S[i], ans, S)


class Solution:

	def permutation(self, S):
		n = len(S)
		ans = []
		self.solve(n, '', S, ans)
		return ans

	def solve(self, n, ip, s, ans):
		if len(s) == 0:
			ans.append(ip)
			return
		if len(s) == n:
			self.solve(n, ip + s[0], s[1:], ans)
		else:
			self.solve(n, ip + ' ' + s[0], s[1:], ans)
			self.solve(n, ip + s[0], s[1:], ans)


class Solution:

	def permutation(self, S):

		def perm(S, i):
			nonlocal cur, res
			if i == len(S) - 1:
				cur += S[-1]
				res.append(cur)
				cur = cur[:-1]
				return
			cur += S[i]
			if i != len(S) - 1:
				cur += ' '
				perm(S, i + 1)
				cur = cur[:-1]
			perm(S, i + 1)
			cur = cur[:-1]
			return
		cur = ''
		res = []
		perm(S, 0)
		return res


class Solution:

	def permutation(self, S):

		def solver(S, ind, temp, N):
			if ind >= N:
				ans.append(temp)
				return
			res1 = temp + S[ind]
			solver(S, ind + 1, res1, N)
			res2 = temp + ' ' + S[ind]
			solver(S, ind + 1, res2, N)
		ans = []
		N = len(S)
		solver(S, 1, S[0], N)
		ans.sort()
		return ans


class Solution:

	def permutation(self, s):
		ip = s[1:]
		op = s[0]
		result = self.p2(ip, op)
		return result

	def p2(self, ip, op):
		result = []
		if len(ip) == 0:
			result.append(op)
			return result
		op1 = op + ' ' + ip[0]
		op2 = op + ip[0]
		ip = ip[1:]
		x = self.p2(ip, op1)
		y = self.p2(ip, op2)
		return x + y


class Solution:

	def permutation(self, S):
		op = ''
		op = op + S[0]
		res = []

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


class Solution:

	def permut(self, inp, op, ans):
		if len(inp) == 0:
			ans.append(''.join(op))
			return
		op1 = op.copy()
		op2 = op.copy()
		op1.append(''.join(' '))
		op1.append(inp[0])
		op2.append(inp[0])
		inp = inp[1:]
		self.permut(inp, op1, ans)
		self.permut(inp, op2, ans)

	def permutation(self, S):
		op = []
		ans = []
		arr = list(S)
		op.append(arr[0])
		inp = arr[1:]
		self.permut(inp, op, ans)
		return ans


class Solution:

	def permutation(self, S):
		res = []
		op = S[0]
		ip = S[1:]

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