Given a string S, Find all the possible subsequences of the String in lexicographically-sorted order.
Example 1:
Input : str = "abc"
Output: a ab abc ac b bc c
Explanation : There are 7 subsequences that 
can be formed from abc.
Example 2:
Input: str = "aa"
Output: a a aa
Explanation : There are 3 subsequences that 
can be formed from aa.
Your Task:
You don't need to read input or print anything. Your task is to complete the function AllPossibleStrings() which takes S as the input parameter and returns a list of all possible subsequences (non-empty) that can be formed from S in lexicographically-sorted order.
Expected Time Complexity: O(n*2^{n}) where n is the length of the String
Expected Space Complexity: O(n * 2^{n})
 
Constraints: 
1 <= Length of String <= 16

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

	def AllPossibleStrings(self, s):

		# Code here

Solutions:
from itertools import combinations

class Solution:

	def AllPossibleStrings(self, s):
		x = []
		for i in range(1, 2 ** len(s)):
			d = ''
			for j in range(len(s)):
				if i & 1 << j:
					d += s[j]
			x.append(d)
		return sorted(x)


class Solution:

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

		def all_sub(st, i, s):
			if i == len(s):
				ans[0].append(st)
				return
			all_sub(st, i + 1, s)
			all_sub(st + s[i], i + 1, s)
			return
		for i in range(len(s)):
			all_sub(s[i], i + 1, s)
		return sorted(ans[0])


import math

class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		power_set = []
		for i in range(2 ** n):
			subset = ''
			j = 0
			for j in range(0, n):
				if i & 1 << j:
					subset += s[j]
			if subset:
				power_set.append(subset)
		power_set.sort()
		return power_set


class Solution:

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

		def dfs(i, subset):
			if i == len(s):
				if len(subset) > 0:
					res.append(subset)
				return
			dfs(i + 1, subset + s[i])
			dfs(i + 1, subset)
		dfs(0, '')
		res.sort()
		return res


class Solution:

	def AllPossibleStrings(self, s):

		def helperFunction(string, index, subsequence, result):
			if index == len(string):
				if subsequence != '':
					result.append(subsequence)
				return
			helperFunction(string, index + 1, subsequence + string[index], result)
			helperFunction(string, index + 1, subsequence, result)
		result = []
		helperFunction(s, 0, '', result)
		return sorted(result)


class Solution(object):

	def AllPossibleStrings(self, s):
		(result, n) = ([], len(s))
		for num in range(2 ** n):
			substring = []
			for index in range(n):
				if num & 1 << index:
					substring.append(s[index])
			if substring:
				result.append(''.join(substring))
		return sorted(result)


class Solution:

	def solve(self, ind, s, ans, tmp):
		if ind >= len(s):
			ans.append(''.join(tmp))
			return ans
		tmp.append(s[ind])
		self.solve(ind + 1, s, ans, tmp)
		tmp.pop()
		self.solve(ind + 1, s, ans, tmp)

	def AllPossibleStrings(self, s):
		if len(s) == 1:
			return s[0]
		i = 0
		ans = []
		tmp = []
		self.solve(i, s, ans, tmp)
		res = []
		for i in ans:
			if i == '':
				continue
			res.append(i)
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):
		n = 2 ** len(s)
		list1 = []
		for i in range(1, n):
			word = ''
			x = i
			j = 0
			while x:
				if x & 1:
					word += s[j]
				x = x >> 1
				j += 1
			list1.append(word)
		return sorted(list1)


class Solution:

	def generator(self, s, index, string):
		if index == len(s):
			if string != '':
				self.res.append(string)
			return
		self.generator(s, index + 1, string + s[index])
		self.generator(s, index + 1, string)

	def AllPossibleStrings(self, s):
		self.res = []
		self.generator(s, 0, '')
		return sorted(self.res)


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		ans = []
		m = 1 << n
		for num in range(1, m):
			sub = ''
			for i in range(0, n):
				if num & 1 << i:
					sub += s[i]
			ans.append(sub)
		return sorted(ans)


class Solution:

	def AllPossibleStrings(self, s):

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


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		a = []
		for i in range(2 ** n):
			subs = ''
			for j in range(n):
				if i & 1 << j == 0:
					subs += s[j]
			if len(subs) > 0:
				a.append(subs)
		a.sort()
		return a


class Solution:

	def gen(self, arr, ch, s, count, leng):
		if count == leng:
			arr.append(ch)
			return
		n = s[0]
		self.gen(arr, ch, s[1:], count + 1, leng)
		self.gen(arr, ch + n, s[1:], count + 1, leng)
		return arr

	def AllPossibleStrings(self, s):
		arr = []
		ch = ''
		self.gen(arr, ch, s, 0, len(s))
		arr = arr[1:]
		arr.sort()
		return arr


class Solution:

	def AllPossibleStrings(self, s):
		sol = []
		a = ''

		def p(i, a):
			if i == len(s):
				sol.append(a.lstrip())
				return
			a += s[i]
			p(i + 1, a)
			a = a[:-1]
			p(i + 1, a)
		p(0, a)
		return sorted(sol)[1:]


class Solution:

	def AllPossibleStrings(self, s):

		def manu(s, st, i, a):
			if i == len(s):
				if st != '':
					a.append(st)
				return
			manu(s, st + s[i], i + 1, a)
			manu(s, st, i + 1, a)
			return
		a = []
		manu(s, '', 0, a)
		return sorted(a)


class Solution:

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

		def recur(st, idx):
			if idx == n:
				res.append(''.join(st))
				return
			st.append(s[idx])
			recur(st, idx + 1)
			st.pop()
			recur(st, idx + 1)
		recur([], 0)
		res.pop()
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):
		res = ['']
		for i in s:
			for j in range(len(res)):
				res.append(res[j] + i)
		res.sort()
		return res[1:]


class Solution:

	def solve(self, i, s, f):
		if i == len(s):
			if len(f) > 0:
				self.res.append(f)
			return
		self.solve(i + 1, s, f + s[i])
		self.solve(i + 1, s, f)

	def AllPossibleStrings(self, s):
		self.res = []
		self.solve(0, s, '')
		self.res.sort()
		return self.res


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		ans = []
		for i in range(0, 1 << n):
			sub = ''
			for j in range(0, n):
				if i & 1 << j != 0:
					sub += s[j]
			if len(sub) > 0:
				ans.append(sub)
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, s):
		string = ''.join(sorted(s))
		subsequence = []
		self.helper(s, subsequence, 0, '')
		subsequence.remove('')
		return sorted(subsequence)

	def helper(self, s, subsequence, index, sub):
		if index == len(s):
			subsequence.append(sub)
			return
		self.helper(s, subsequence, index + 1, sub)
		self.helper(s, subsequence, index + 1, sub + s[index])
		return


class Solution:

	def AllPossibleStrings(self, str):
		if len(str) == 0:
			return []
		char = str[0]
		remaining_string = str[1:]
		li = self.AllPossibleStrings(remaining_string)
		new_list = []
		for i in li:
			new_list.append(i)
			new_list.append(char + i)
		new_list.append(char)
		return sorted(new_list)


from itertools import chain, combinations

class Solution:

	def AllPossibleStrings(self, s):
		res = []
		for each in list(map(list, chain.from_iterable((combinations(s, r) for r in range(1, len(s) + 1))))):
			res.append(''.join(each))
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):
		ans = []
		for i in range(1, 2 ** len(s)):
			str = ''
			for j in range(len(s)):
				if i & 1 << j:
					str = str + s[j]
			ans.append(str)
		ans.sort()
		return ans


class Solution:

	def substring(self, b, a, s, i):
		if i >= len(s):
			if len(a) != 0:
				b.append(''.join(a))
			return
		else:
			self.substring(b, a.copy(), s, i + 1)
			element = s[i]
			a.append(element)
			self.substring(b, a.copy(), s, i + 1)
			return b

	def AllPossibleStrings(self, s):
		a = []
		b = []
		i = 0
		y = self.substring(b, a, s, i)
		return sorted(y)


class Solution:

	def AllPossibleStrings(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, res)
		res = []
		helper(s, 0, '', res)
		res.sort()
		return res[1:]


class Solution:

	def AllPossibleStrings(self, s):
		set_size = pow(2, len(s))
		ans = []
		for counter in range(0, set_size):
			a = ''
			for j in range(0, len(s)):
				if counter & 1 << j > 0:
					a += s[j]
			ans.append(a)
		return sorted(ans[1:])


from itertools import combinations

class Solution:

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

		def dfs(ind, path, ans):
			if ans != '':
				ans.append(path)
			if ind == len(s):
				return
			for i in range(ind, len(s)):
				dfs(i + 1, path + s[i], ans)
		dfs(0, '', ans)
		return sorted(ans[1:])


class Solution:

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

		def util(res, s, sub, index):
			for i in range(index, len(s)):
				temp = sub + s[i]
				res.append(temp)
				util(res, s, temp, i + 1)
			return
		util(res, s, '', 0)
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):
		res = []
		for i in range(2 ** len(s)):
			str = ''
			for j in range(len(s)):
				if i & 1 << j:
					str += s[j]
			res.append(str)
		return sorted(res)[1:]


class Solution:

	def AllPossibleStrings(self, s):
		nums = [i for i in s]
		ans = []
		n = len(nums)
		for i in range(1 << n):
			st = ''
			for bit in range(n):
				if i >> bit & 1:
					st = st + nums[bit]
			if len(st) != 0:
				ans.append(st)
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, S):
		n = len(S)
		subsequences = []
		for i in range(1, 1 << n):
			subseq = ''
			for j in range(n):
				if i & 1 << j:
					subseq += S[j]
			subsequences.append(subseq)
		subsequences.sort()
		return subsequences


class Solution:

	def AllPossibleStrings(self, s):

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


class Solution:

	def AllPossibleStrings(self, s):
		ans = []
		n = len(s)
		for i in range(1, pow(2, n)):
			res = ''
			for j in range(n):
				if 1 << j & i:
					res += s[j]
			if len(res) > 0:
				ans.append(res)
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, s):
		subsequences = []
		for i in range(2 ** len(s)):
			sub = ''
			for j in range(len(s)):
				if i & 1 << j:
					sub += s[j]
			if len(sub) > 0:
				subsequences.append(sub)
		result = sorted(subsequences)
		return result


class Solution:

	def subsets(self, s, i, ans, tmp):
		if i == len(s):
			ans.append(tmp)
			return
		self.subsets(s, i + 1, ans, tmp)
		self.subsets(s, i + 1, ans, tmp + s[i])

	def AllPossibleStrings(self, s):
		ans = []
		self.subsets(s, 0, ans, '')
		ans.remove('')
		ans.sort()
		return ans


class Solution:

	def solve(self, i, s, ans, k):
		if i == len(s):
			ans.append(''.join(k))
			return
		k.append(s[i])
		self.solve(i + 1, s, ans, k)
		k.pop()
		self.solve(i + 1, s, ans, k)

	def AllPossibleStrings(self, s):
		ans = []
		k = []
		self.solve(0, s, ans, k)
		return sorted(ans)[1:]


def check(string, index, n, cur, s1):
	if index == n:
		s1.append(cur)
		return
	check(string, index + 1, n, cur + s[index], s1)
	check(string, index + 1, n, cur, s1)

class Solution:

	def AllPossibleStrings(self, s):
		s1 = []
		check(s, 0, len(s), '', s1)
		s1.sort()
		return s1[1:]


class Solution:

	def substrs(self, s, i, arr, cs):
		if i == len(s):
			arr.append(cs)
			return
		self.substrs(s, i + 1, arr, cs + s[i])
		self.substrs(s, i + 1, arr, cs)

	def AllPossibleStrings(self, s):
		arr = []
		self.substrs(s, 0, arr, '')
		arr.sort()
		return arr[1:]


class Solution:

	def my_function(self, s, ans, i, main_list):
		if i >= len(s):
			main_list.append(ans)
		else:
			self.my_function(s, ans + s[i], i + 1, main_list)
			self.my_function(s, ans, i + 1, main_list)

	def AllPossibleStrings(self, s):
		ans = ''
		i = 0
		main_list = []
		self.my_function(s, ans, i, main_list)
		main_list = main_list[:-1]
		main_list.sort()
		return main_list


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		ans = []
		for num in range(1, 1 << n):
			str = ''
			for i in range(n):
				if num & 1 << i:
					str += s[i]
			ans.append(str)
		return sorted(ans)


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		no_of_subsets = 2 ** n
		subsets = []
		grid = [[0 for _ in range(n)] for _ in range(no_of_subsets)]
		for i in range(1, no_of_subsets):
			x = i
			for ct in range(n):
				grid[i][ct] = 1 if x & 1 != 0 else 0
				x = x >> 1
		for i in range(1, no_of_subsets):
			subset = ''
			for j in range(n):
				if grid[i][j] == 1:
					subset += s[j]
			subsets.append(subset)
		return sorted(subsets)


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		p = 2 ** n
		res = []
		for i in range(1, p):
			tmp = ''
			for j in range(n):
				if i & 1 << j:
					tmp += s[j]
			res.append(tmp)
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):
		return sorted(self.rec(s, '', 0, []))

	def rec(self, s, curr, i, arr):
		if i == len(s):
			if curr != '':
				arr.append(curr)
			return
		self.rec(s, curr + s[i], i + 1, arr)
		self.rec(s, curr, i + 1, arr)
		return arr


class Solution:

	def AllPossibleStrings(self, s):
		output = []
		for val in range(1, 2 ** len(s)):
			currentString = ''
			for j in range(len(s)):
				if val & 1 << j:
					currentString += s[j]
			output.append(currentString)
		return sorted(output)


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		res = []
		ran = 1 << n
		for i in range(ran):
			temp = ''
			for j in range(n):
				if i & 1 << j != 0:
					temp += s[j]
			if temp:
				res.append(temp)
		res = sorted(res)
		return res


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		size = 2 ** n
		res = []
		for i in range(1, size):
			num = i
			idx = 0
			ans = []
			while num:
				val = num & 1
				if val:
					ans.append(s[idx])
				num >>= 1
				idx += 1
			res.append(''.join(ans))
		return sorted(res)


class Solution:

	def AllPossibleStrings(self, s):

		def recursion(ind, ans):
			if ans != '':
				res.append(ans)
			if ind >= len(s):
				return
			for i in range(ind, len(s)):
				recursion(i + 1, ans + s[i])
		res = []
		recursion(0, '')
		return sorted(res)


import math

class Solution:

	def AllPossibleStrings(self, s):
		new_s = []
		powerSetSize = int(math.pow(2, len(s)))
		for counter in range(0, powerSetSize):
			val = ''
			for j in range(0, len(s)):
				if counter & 1 << j > 0:
					val += s[j]
			new_s.append(val)
		return sorted(new_s)[1:]


class Solution:

	def power_set(self, ans, idx, s, n, curr):
		if idx == n:
			if curr != '':
				ans.append(curr)
			return
		self.power_set(ans, idx + 1, s, n, curr)
		self.power_set(ans, idx + 1, s, n, curr + s[idx])

	def AllPossibleStrings(self, s):
		ans = []
		idx = 0
		n = len(s)
		curr = ''
		self.power_set(ans, idx, s, n, curr)
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, nums):
		n = len(nums)
		l1 = []
		for i in range(0, 2 ** n):
			l = ''
			for j in range(n):
				if i & 1 << j != 0:
					l += nums[j]
			l1.append(l)
		l1.sort()
		return l1[1:]


from itertools import combinations

class Solution:

	def AllPossibleStrings(self, s):
		ans = []
		for i in range(0, len(s) + 1):
			for element in combinations(s, i):
				ans.append(''.join(element))
		ans.remove('')
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		ans = []
		for i in range(1, 1 << n):
			l = []
			for j in range(n):
				if 1 << j & i:
					l.append(s[j])
			ans.append(''.join(l))
		return sorted(ans)


class Solution:

	def helper(self, str, idx, temp):
		if len(str) == idx:
			return temp
		str2 = self.helper(str, idx + 1, temp + str[idx])
		str1 = self.helper(str, idx + 1, temp)
		if type(str1) == list:
			return str1 + str2
		else:
			return [str1, str2]

	def AllPossibleStrings(self, s):
		result = self.helper(s, 0, '')
		return [x for x in sorted(result) if x]


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		res = []
		for num in range(1 << n):
			ds = []
			for bit in range(n):
				if num & 1 << bit != 0:
					ds.append(s[bit])
			if ds:
				res.append(''.join(ds))
		return sorted(res)


class Solution:

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

		def sub(i, temp, s, res):
			if i >= n:
				res.append(temp)
				return res
			temp += s[i]
			sub(i + 1, temp, s, res)
			temp = temp[:-1]
			sub(i + 1, temp, s, res)
			return res
		final = sub(0, '', s, [])
		final.sort()
		final.remove('')
		return final


class Solution:

	def AllPossibleStrings(self, s):
		size = len(s)
		power_size = int(2 ** len(s))
		l = [0] * power_size
		for i in range(power_size):
			r = ''
			for j in range(size):
				if i & 1 << j > 0:
					r += s[j]
			l[i] = r
		l.sort()
		return l[1:]


class Solution:

	def solve(self, i, s, li, ans):
		if i == len(s):
			ans.append(li)
			return
		self.solve(i + 1, s, li, ans)
		self.solve(i + 1, s, li + s[i], ans)
		return ans

	def AllPossibleStrings(self, s):
		a = self.solve(0, s, '', [])
		a.sort()
		a.remove('')
		return a


class Solution:

	def AllPossibleStrings(self, s):
		n = 1 << len(s)
		c = []
		for i in range(1, n):
			d = ''
			for j in range(32):
				if i >> j & 1 == 1:
					d += s[j]
			c.append(d)
		c.sort()
		return c


class Solution:

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

		def fun(i, n, l=[]):
			if i == n:
				x = ''.join(l)
				if l:
					res.append(x)
				return
			l.append(s[i])
			fun(i + 1, n, l)
			l.pop()
			fun(i + 1, n, l)
		fun(0, len(s))
		res.sort()
		return res


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		sub = []
		for i in range(1, 1 << n):
			temp = []
			for j in range(n):
				if i >> j & 1:
					temp.append(s[j])
			sub.append(''.join(temp))
		return sorted(sub)


class Solution:

	def AllPossibleStrings(self, s):
		inp = s
		out = ''
		sub = []

		def subset(inp, out, sub):
			if len(inp) == 0:
				sub.append(out)
				return
			out1 = out
			out2 = out
			out2 = out2 + inp[0]
			inp = inp[1:]
			subset(inp, out1, sub)
			subset(inp, out2, sub)
			return
		subset(inp, out, sub)
		sub.sort()
		sub.pop(0)
		return sub


class Solution:

	def recur(self, i, s, ans, n, arr):
		if i == n:
			if ans != '':
				arr.append(ans)
			return
		not_pick = self.recur(i + 1, s, ans, n, arr)
		pick = self.recur(i + 1, s, ans + s[i], n, arr)

	def AllPossibleStrings(self, s):
		arr = []
		self.recur(0, s, '', len(s), arr)
		return sorted(arr)


class Solution:

	def AllPossibleStrings(self, s):
		(N, ans) = (len(s), [])
		for v in range(1, 2 ** N):
			(L, i) = ([], 0)
			while v:
				if v & 1:
					L.append(s[i])
				v >>= 1
				i += 1
			ans.append(''.join(L))
		return sorted(ans)


class Solution:

	def AllPossibleStrings(self, s):
		letter = [x for x in s]
		possible_strs = list()
		for num in range(1, pow(2, len(s))):
			curr_string = ''
			idx = 0
			while num:
				if num & 1:
					curr_string += letter[idx]
				num >>= 1
				idx += 1
			possible_strs.append(curr_string)
		possible_strs.sort()
		return possible_strs


class Solution:

	def AllPossibleStrings(self, s):
		ans = []
		opt = [1, 0]
		N = len(s)
		i = 0
		str = ''
		self.answer(str, i, s, opt, N, ans)
		ans.sort()
		ans.remove('')
		return ans

	def answer(self, str, i, s, opt, N, ans):
		if i == N:
			ans.append(str)
		else:
			self.answer(str + s[i], i + 1, s, opt, N, ans)
			self.answer(str, i + 1, s, opt, N, ans)


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)
		res = []
		for i in range(2 ** n):
			subsequence = ''
			for j in range(n):
				if i & 1 << j:
					subsequence += s[j]
			if len(subsequence) > 0:
				res.append(subsequence)
		res = sorted(res)
		return res


class Solution:

	def isIthBitSet(self, num, i):
		if num & 1 << i:
			return True
		return False

	def AllPossibleStrings(self, s):
		n = len(s)
		tn = pow(2, n)
		res = []
		for num in range(1, tn):
			sub = ''
			for i in range(n):
				if self.isIthBitSet(num, i):
					sub += s[i]
			res.append(sub)
		res.sort()
		return res


class Solution:

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

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


class Solution:

	def AllPossibleStrings(self, s):
		n = len(s)

		def rec(s, i, path, ans):
			if i == n:
				if path:
					ans.append(path)
				return
			p = rec(s, i + 1, path + s[i], ans)
			np = rec(s, i + 1, path, ans)
		ans = []
		rec(s, 0, '', ans)
		ans.sort()
		return ans


class Solution:

	def AllPossibleStrings(self, str1):
		n = len(str1)
		res = []
		for num in range(0, 1 << n):
			subStr = ''
			for i in range(0, n):
				if num & 1 << i:
					subStr += str1[i]
			res.append(subStr)
			subStr = ''
		res = res[1:]
		res.sort()
		return res


class Solution:

	def solve(self, inn, out, ans):
		if len(inn) == 0:
			if out != '':
				ans.append(out)
			return
		self.solve(inn[1:], out + inn[0], ans)
		self.solve(inn[1:], out, ans)

	def AllPossibleStrings(self, s):
		inn = s
		if s == '':
			return []
		out = ''
		ans = []
		self.solve(inn, out, ans)
		ans.sort()
		return ans