Given an integer N , Print all binary strings of size N which do not contain consecutive 1s.
A binary string is that string which contains only 0 and 1.
Example 1:
Input:
N = 3
Output:
000 , 001 , 010 , 100 , 101
Explanation:
None of the above strings contain consecutive 1s. "110" is not an answer as it has '1's occuring consecutively. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function generateBinaryStrings() which takes an integer N as input and returns a list of all valid binary strings in lexicographically increasing order.
Expected Time Complexity: O(2^{N})
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 20

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def generateBinaryStrings(self, n):

        # Code here

Solutions:
class Solution:

	def generateBinaryStrings(self, n):

		def recursion(arr, n, ans):
			if n == 0:
				ans.append(arr)
				return ans
			recursion(arr + '0', n - 1, ans)
			if len(arr) == 0 or arr[-1] != '1':
				recursion(arr + '1', n - 1, ans)
			return ans
		return recursion('', n, [])


class Solution:

	def genBin(self, s, n):
		if n == 0:
			self.ans.append(s)
		elif s == '':
			self.genBin(s + '0', n - 1)
			self.genBin(s + '1', n - 1)
		elif s[-1] == '1':
			self.genBin(s + '0', n - 1)
		else:
			self.genBin(s + '0', n - 1)
			self.genBin(s + '1', n - 1)

	def generateBinaryStrings(self, n):
		self.ans = []
		self.genBin('', n)
		return self.ans


class Solution:

	def generateBinaryStrings(self, n):
		flag = True
		ans = []
		self.solve(0, flag, n, ans, [])
		return ans

	def solve(self, i, flag, n, ans, l):
		if i == n:
			t = ''
			for k in range(len(l)):
				t += l[k]
			ans.append(t)
			return
		if flag == True:
			l.append('0')
			self.solve(i + 1, flag, n, ans, l)
			l.pop()
			flag = False
			l.append('1')
			self.solve(i + 1, flag, n, ans, l)
			l.pop()
		else:
			flag = True
			l.append('0')
			self.solve(i + 1, flag, n, ans, l)
			l.pop()


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def f(i, cur):
			if i == n:
				ans.append(cur)
				return
			f(i + 1, cur + '0')
			if len(cur) == 0 or cur[-1] != '1':
				f(i + 1, cur + '1')
		f(0, '')
		return ans


class Solution:

	def gen(self, pos, n, num):
		if pos == n:
			self.l.append(num)
			return
		self.gen(pos + 1, n, num + '0')
		if num == '' or num[-1] == '0':
			self.gen(pos + 1, n, num + '1')

	def generateBinaryStrings(self, n):
		self.l = []
		self.gen(0, n, '')
		return self.l


class Solution:

	def generate(self, pos, n, num):
		if pos == n:
			self.L.append(num)
			return
		self.generate(pos + 1, n, num + '0')
		if num == '' or num[-1] == '0':
			self.generate(pos + 1, n, num + '1')

	def generateBinaryStrings(self, n):
		self.L = list()
		self.generate(0, n, '')
		return self.L


class Solution:

	def generateBinaryStrings(self, n):
		last = 2 ** n - 1
		L = list()
		for i in range(last + 1):
			s = str(bin(i))
			s1 = s[2:]
			if '11' not in s:
				while len(s1) < n:
					s1 = '0' + s1
				L.append(s1)
		return L


class Solution:

	def generateBinaryStrings(self, n):
		c = 0
		l = []
		while c < 2 ** n:
			b = str(bin(c))
			if '11' not in b:
				l1 = len(b)
				b = b[2:]
				while len(b) != n:
					b = '0' + b
				l.append(b)
			c += 1
		return l


class Solution:

	def generateBinaryStrings(self, n):
		ans = [[]]

		def make(s, n):
			if len(s) == n:
				ans[0].append(s)
				return
			if s[-1] == '0':
				make(s + '0', n)
				make(s + '1', n)
			else:
				make(s + '0', n)
			return
		make('0', n)
		make('1', n)
		return ans[0]
		return sorted(ans[0])


class Solution:

	def generateBinaryStrings(self, n):
		self.res = []
		self.helper(0, n, '')
		return self.res

	def helper(self, pos, n, num):
		if pos == n:
			self.res.append(num)
			return
		self.helper(pos + 1, n, num + '0')
		if num == '' or num[-1] == '0':
			self.helper(pos + 1, n, num + '1')


class Solution:

	def generateBinaryStrings(self, n):
		res = []

		def generate(n, i, subset):
			if i == n:
				res.append(subset.copy())
				return
			if i != 0 and subset[-1] == '1':
				subset.append('0')
				generate(n, i + 1, subset)
				subset.pop()
			else:
				subset.append('0')
				generate(n, i + 1, subset)
				subset.pop()
				subset.append('1')
				generate(n, i + 1, subset)
				subset.pop()
		generate(n, 0, [])
		for i in range(len(res)):
			res[i] = ''.join(res[i])
		return res


class Solution:

	def generateBinaryStrings(self, n):
		res = []
		s = []
		self.f(0, res, s, n)
		return res

	def f(self, ind, res, s, n):
		if len(s) >= 2 and (s[-1] == '1' and s[-2] == '1'):
			return
		if ind >= n:
			if len(s) == n:
				res.append(''.join(s))
			return
		s.append('0')
		self.f(ind + 1, res, s, n)
		s.pop()
		s.append('1')
		self.f(ind + 1, res, s, n)
		s.pop()


class Solution:

	def solve(self, k, n, curr):
		if k == n:
			self.ans.append(''.join(curr))
			return
		curr.append('0')
		self.solve(k + 1, n, curr)
		curr.pop()
		if len(curr) == 0 or curr[-1] == '0':
			curr.append('1')
			self.solve(k + 1, n, curr)
			curr.pop()

	def generateBinaryStrings(self, n):
		self.ans = []
		self.solve(0, n, [])
		return self.ans


class Solution:

	def fun(self, n, str, ind):
		if ind == n:
			return self.res.append(str)
		self.fun(n, str + '0', ind + 1)
		if str == '' or str[-1] == '0':
			self.fun(n, str + '1', ind + 1)

	def generateBinaryStrings(self, n):
		self.res = []
		self.fun(n, '', 0)
		return self.res


class Solution(object):

	def generateBinaryStrings(self, n):

		def generateBits(chars, index):
			if index == n:
				result.append(chars)
				return
			generateBits(chars + '0', index + 1)
			if chars != '' and chars[-1] == '1':
				return
			generateBits(chars + '1', index + 1)
		result = []
		generateBits('', 0)
		return result


class Solution:

	def boobs(self, str, n, res):
		l = len(str)
		if l == n:
			res.append(str)
			return
		elif str[-1] == '0':
			self.boobs(str + '0', n, res)
			self.boobs(str + '1', n, res)
		else:
			self.boobs(str + '0', n, res)

	def generateBinaryStrings(self, n):
		res = []
		word = '0'
		self.boobs(word, n, res)
		word = '1'
		self.boobs(word, n, res)
		return res


class Solution:

	def generateBinaryStrings(self, n, stringsofar=''):
		if not hasattr(self, 'res'):
			self.res = []
		if n == 0:
			self.res.append(stringsofar)
			return self.res
		if len(stringsofar) == 0:
			self.generateBinaryStrings(n - 1, '0')
			self.generateBinaryStrings(n - 1, '1')
		else:
			self.generateBinaryStrings(n - 1, stringsofar + '0')
			if stringsofar[-1] != '1':
				self.generateBinaryStrings(n - 1, stringsofar + '1')
		return self.res


class Solution:

	def binaryString(self, n, str, curr_idx, arr):
		if curr_idx == n:
			return arr.append(str)
		if curr_idx != 0 and str[curr_idx - 1] == '1':
			self.binaryString(n, str + '0', curr_idx + 1, arr)
		else:
			self.binaryString(n, str + '0', curr_idx + 1, arr)
			self.binaryString(n, str + '1', curr_idx + 1, arr)

	def generateBinaryStrings(self, n):
		arr = []
		self.binaryString(n, '', 0, arr)
		return arr


class Solution:

	def generateBinaryStrings(self, n):
		if n == 1:
			return ['0', '1']
		else:
			temp = self.generateBinaryStrings(n - 1)
			ans = []
			for item in temp:
				if item[0] == '0':
					ans.append('0' + item)
					ans.append('1' + item)
				else:
					ans.append('0' + item)
			ans.sort()
			return ans


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def dfs(ind, s, chk):
			if ind == n:
				ans.append(s[:])
				return
			dfs(ind + 1, s + '0', False)
			if not chk:
				dfs(ind + 1, s + '1', True)
		dfs(0, '', False)
		return ans


class Solution:

	def generateBinaryStrings(self, n):

		def rec(curr, i):
			if i == n:
				ans.append(curr)
				return
			rec(curr + '0', i + 1)
			if len(curr) == 0 or curr[-1] != '1':
				rec(curr + '1', i + 1)
		ans = []
		rec('', 0)
		return ans


def rec(cur, n, ans):
	if n == 0:
		ans.append(cur)
		return
	rec(cur + '0', n - 1, ans)
	if len(cur) == 0 or (len(cur) > 0 and cur[-1] != '1'):
		rec(cur + '1', n - 1, ans)

class Solution:

	def generateBinaryStrings(self, n):
		ans = []
		rec('', n, ans)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		l = []
		s = ''

		def rec(ind, p, s):
			if ind == n:
				l.insert(0, s)
				return
			if p == 0:
				s += '1'
				rec(ind + 1, 1, s)
				s = s[:len(s) - 1]
				s += '0'
				rec(ind + 1, 0, s)
				s = s[:len(s) - 1]
			else:
				s += '0'
				rec(ind + 1, 0, s)
				s = s[:len(s) - 1]
		rec(0, 0, '')
		return l


class Solution:

	def generateBinaryStrings(self, n):
		res = []

		def recur(string):
			if len(string) == n:
				res.append(string[:])
				return
			if not string or string[-1] == '0':
				recur(string + '1')
				recur(string + '0')
			else:
				recur(string + '0')
		recur('')
		res.sort()
		return res


class Solution:

	def generateBinaryStrings(self, n):
		result = []

		def solve(idx, tillNow):
			if idx == n:
				result.append(tillNow)
				return
			solve(idx + 1, tillNow + '0')
			if len(tillNow) >= 1 and tillNow[-1] != '1':
				solve(idx + 1, tillNow + '1')
		solve(1, '0')
		solve(1, '1')
		return result


class Solution:

	def generateBinaryStrings(self, n):
		a = []

		def p(x, b):
			if len(x) == n:
				a.append(x)
			else:
				if b == '0':
					p(x + b, '1')
				p(x + b, '0')
		p('', '0')
		p('', '1')
		return sorted(set(a))


class Solution:

	def solve(self, n, index, path, ans):
		if index == n:
			ans.append(path)
			return ans
		if index != 0 and path[index - 1] == '1':
			self.solve(n, index + 1, path + '0', ans)
		else:
			self.solve(n, index + 1, path + '0', ans)
			self.solve(n, index + 1, path + '1', ans)

	def generateBinaryStrings(self, n):
		path = ''
		ans = []
		index = 0
		self.solve(n, index, path, ans)
		return sorted(ans)


class Solution:

	def solve(self, pos, n, ans):
		if pos == n:
			self.res.append(ans)
			return
		self.solve(pos + 1, n, ans + '0')
		if ans == '' or ans[-1] == '0':
			self.solve(pos + 1, n, ans + '1')

	def generateBinaryStrings(self, n):
		self.res = []
		self.solve(0, n, '')
		return self.res


class Solution:

	def generateBinaryStrings(self, n):
		binary = ['0', '1']
		if n == 1:
			return binary
		count = []
		binary_num = 2
		return self.helper(n, binary_num, binary, count)

	def helper(self, n, binary_num, binary, count):
		if binary_num > n:
			return binary
		for num in binary:
			count.append(num + '0')
			if num[-1] != '1':
				count.append(num + '1')
		return self.helper(n, binary_num + 1, count, [])


class Solution:

	def rec(self, i, n, s, res):
		if i == n:
			res.append(s)
			return
		self.rec(i + 1, n, s + '0', res)
		if i == 0 or s[i - 1] == '0':
			self.rec(i + 1, n, s + '1', res)

	def generateBinaryStrings(self, n):
		res = []
		self.rec(0, n, '', res)
		return res


class Solution:

	def generateBinaryStrings(self, n):

		def binaryStrings(arr, idx):
			if idx == len(arr):
				res.append(''.join(arr))
				return
			binaryStrings(arr, idx + 1)
			ac = arr.copy()
			if idx != 0:
				if ac[len(ac) - idx] != '1':
					ac[len(ac) - 1 - idx] = '1'
					binaryStrings(ac, idx + 1)
			else:
				ac[-1] = '1'
				binaryStrings(ac, idx + 1)
		res = []
		arr = ['0'] * n
		binaryStrings(arr, 0)
		res.sort()
		return res


class Solution:

	def print_binary(self, n, last_digit):
		if n == 0:
			return ['']
		result = []
		if last_digit == 0:
			for s in self.print_binary(n - 1, 0):
				result.append('0' + s)
			for s in self.print_binary(n - 1, 1):
				result.append('1' + s)
		else:
			for s in self.print_binary(n - 1, 0):
				result.append('0' + s)
		return result

	def generateBinaryStrings(self, n):
		return self.print_binary(n, 0)


class Solution:

	def generateBinaryStrings(self, n):

		def greet(a, s):
			if len(s) == n:
				a.append(s)
				return
			else:
				greet(a, s + '0')
				if len(s) == 0 or s[-1] == '0':
					greet(a, s + '1')
			return a
		return greet([], '')


class Solution:

	def generateBinaryStrings(self, n):
		if n == 1:
			return ['0', '1']
		else:
			prev_strings = self.generateBinaryStrings(n - 1)
			new_strings = []
			for string in prev_strings:
				new_strings.append(string + '0')
				if string[-1] == '0':
					new_strings.append(string + '1')
			return new_strings


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def bin(i, s):
			if i == n:
				ans.append(s)
				return
			bin(i + 1, s + '0')
			if len(s) == 0 or s[-1] != '1':
				bin(i + 1, s + '1')
			return
		bin(0, '')
		return ans


class Solution:

	def generate_binary(self, n, temp, last_digit, ans):
		if n == 0:
			ans.append(temp)
			return
		self.generate_binary(n - 1, temp + '0', '0', ans)
		if last_digit == '0':
			self.generate_binary(n - 1, temp + '1', '1', ans)

	def generateBinaryStrings(self, n):
		ans = []
		self.generate_binary(n, '', '0', ans)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		res = []
		self.helper('', n, res)
		return res

	def helper(self, ans, n, res):
		if len(ans) == n:
			res.append(ans)
			return
		if len(ans) == 0 or ans[-1] == '0':
			self.helper(ans + '0', n, res)
			self.helper(ans + '1', n, res)
		else:
			self.helper(ans + '0', n, res)


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def helper(ans, string, n):
			if n == 1:
				ans.append(string)
			elif string[-1] == '0':
				helper(ans, string + '0', n - 1)
				helper(ans, string + '1', n - 1)
			else:
				helper(ans, string + '0', n - 1)
		helper(ans, '0', n)
		helper(ans, '1', n)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		l = ['0', '1']
		res = []

		def solve(l, n):
			if n == 0:
				return l
			res = []
			for i in range(len(l)):
				ele = l[i]
				ele1 = l[i] + '0'
				res.append(ele1)
				if ele[-1] != '1':
					ele2 = l[i] + '1'
					res.append(ele2)
			return solve(res, n - 1)
		return solve(l, n - 1)


class Solution:

	def generateBinaryStrings(self, n):
		s = ['0'] * n
		ans = []
		self.binary(n, 0, s, ans)
		return ans[::-1]

	def binary(self, n, i, s, ans):
		if i > n - 1:
			ans.append(''.join(s))
			return
		s[i] = '1'
		self.binary(n, i + 2, s, ans)
		s[i] = '0'
		self.binary(n, i + 1, s, ans)


class Solution:

	def generateBinaryStrings(self, n):
		ans = []
		stri = ''

		def funcall(index, n, stri):
			if index == n:
				ans.append(stri)
				return
			funcall(index + 1, n, stri + '0')
			if len(stri) == 0 or stri[-1] == '0':
				funcall(index + 1, n, stri + '1')
		funcall(0, n, stri)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		l1 = []
		final = []
		pattern = '11'
		for i in range(pow(2, n)):
			val = bin(i).replace('0b', '')
			val = str(val).zfill(n)
			l1.append(val)
		for i in l1:
			if pattern not in i:
				final.append(i)
		return final


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def f(res, size):
			if size >= n:
				ans.append(''.join(res))
				return
			res.append('0')
			f(res, size + 1)
			res.pop()
			if len(res) == 0 or res[-1] != '1':
				res.append('1')
				f(res, size + 1)
				res.pop()
		f([], 0)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		res = []

		def solve(t):
			if len(t) == n:
				res.append(t)
				return
			if t[-1] == '0':
				solve(t + '0')
				solve(t + '1')
			else:
				solve(t + '0')
		solve('0')
		solve('1')
		return res


class Solution:

	def recur(self, val, st, n, height, out):
		if height == n:
			st += val
			out.append(st)
			return
		st += val
		self.recur('0', st, n, height + 1, out)
		if val != '1':
			self.recur('1', st, n, height + 1, out)

	def generateBinaryStrings(self, n):
		out = []
		self.recur('', '', n, 0, out)
		return out


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def strings(self, n, buff, ans):
		if n == 0:
			ans.append(buff)
		elif n > 0:
			self.strings(n - 1, buff + '0', ans)
			if not buff or buff[-1] == '0':
				self.strings(n - 1, buff + '1', ans)

	def generateBinaryStrings(self, n):
		ans = []
		self.strings(n, '', ans)
		return ans


class Solution:

	def util(self, i, n, res, s):
		if i == n:
			res.append(s)
			return
		else:
			self.util(i + 1, n, res, s + '0')
			if i == 0 or s[i - 1] == '0':
				self.util(i + 1, n, res, s + '1')

	def generateBinaryStrings(self, n):
		res = []
		self.util(0, n, res, '')
		return res


class Solution:

	def generateBinaryStrings(self, n):
		zero = '0'
		series = []
		fl = []
		flag = 0
		pattern = '11'
		for i in range(pow(2, n)):
			temp = str(bin(i)[2:])
			while len(temp) < n:
				temp = zero + temp
			series.append(temp)
		for i in series:
			if pattern in i:
				continue
			fl.append(i)
		return fl


class Solution:

	def generateBinaryStrings(self, n):

		def recursion(ans, n):
			if n <= 0:
				t.append(ans)
				return
			if ans == '' or ans[-1] == '0':
				recursion(ans + '1', n - 1)
			recursion(ans + '0', n - 1)
		t = []
		recursion('', n)
		return sorted(t)


class Solution:

	def generateBinaryStrings(self, n):
		l = []

		def rec(t):
			if len(t) == n:
				l.append(t)
				return
			if t[-1] == '0':
				rec(t + '0')
				rec(t + '1')
			else:
				rec(t + '0')
		rec('0')
		rec('1')
		return l


class Solution:

	def generateBinaryStrings(self, n):
		final = []

		def call(arr: list, s):
			if s == n:
				final.append(arr[:])
				return
			arr.append('0')
			call(arr, s + 1)
			arr.pop()
			if arr != []:
				if arr[-1] != '1':
					arr.append('1')
					call(arr, s + 1)
					arr.pop()
			else:
				arr.append('1')
				call(arr, s + 1)
				arr.pop()
		call([], 0)
		f = []
		for i in final:
			x = ''.join(i)
			f.append(x)
		return f


class Solution:

	def generateBinaryStrings(self, n):
		ans = []
		self.binary(n, ans)
		return ans

	def binary(self, n, biList, curr=''):
		if len(curr) == n:
			return biList.append(curr)
		self.binary(n, biList, curr + '0')
		if not curr or (curr and curr[-1] != '1'):
			self.binary(n, biList, curr + '1')


class Solution:

	def gen(self, arr, ch, n):
		if len(ch) == n + 1:
			return
		if len(ch) == n:
			arr.append(ch)
		self.gen(arr, ch + '0', n)
		if len(ch) == 0 or ch[len(ch) - 1] != '1':
			self.gen(arr, ch + '1', n)
		return arr

	def generateBinaryStrings(self, n):
		arr = []
		ch = ''
		self.gen(arr, ch, n)
		return arr


class Solution:

	def generateBinaryStrings(self, n):
		a = ['0', '1']
		while n > 1:
			l = len(a)
			for ele in a[:]:
				g = ele + '0'
				a.append(g)
				if ele[-1] == '1':
					continue
				else:
					a.append(ele + '1')
			a = a[l:]
			n -= 1
		return a


class Solution:

	def generateBinaryStrings(self, n):
		i = 0
		str = ''
		ans = []
		self.helper(str, i, n, ans)
		return ans

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


class Solution:

	def generateBinaryStrings(self, n):
		res = []
		self.generate(0, n, '', res)
		return res

	def generate(self, i, n, string, res):
		if i == n:
			res.append(string)
			return
		self.generate(i + 1, n, string + '0', res)
		if not string or string[-1] != '1':
			self.generate(i + 1, n, string + '1', res)


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def go(n, s):
			if n == 0:
				ans.append(s)
				return
			go(n - 1, s + '0')
			if s[-1] != '1':
				go(n - 1, s + '1')
		go(n - 1, '0')
		go(n - 1, '1')
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		if n == 1:
			return ['0', '1']
		temp_l = self.generateBinaryStrings(n - 1)
		og_list = []
		for i in range(len(temp_l)):
			if temp_l[i][-1] == '1':
				og_list.append(temp_l[i] + '0')
			else:
				og_list.append(temp_l[i] + '0')
				og_list.append(temp_l[i] + '1')
		return og_list


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def generate(s):
			if len(s) == n:
				ans.append(s)
				return
			elif len(s) > 0 and s[-1] == '1':
				generate(s + '0')
			else:
				generate(s + '0')
				generate(s + '1')
		generate('')
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		ans = []
		li = []

		def helper(i, n, ans, li):
			if i == n:
				s = ''.join((ele for ele in li))
				ans.append(s)
				return
			if i != 0 and li[-1] == '1':
				li.append('0')
				helper(i + 1, n, ans, li)
				li.pop()
			else:
				li.append('0')
				helper(i + 1, n, ans, li)
				li.pop()
				li.append('1')
				helper(i + 1, n, ans, li)
				li.pop()
		helper(0, n, ans, li)
		return ans


class Solution:

	def recur(self, n, s, i, ans):
		if n == i:
			ans.append(s)
			return
		if i != 0 and s[i - 1] == '1':
			self.recur(n, s + '0', i + 1, ans)
		else:
			self.recur(n, s + '0', i + 1, ans)
			self.recur(n, s + '1', i + 1, ans)

	def generateBinaryStrings(self, n):
		ans = []
		self.recur(n, '', 0, ans)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		output = set()

		def recurBinary(binaryStr):
			if len(binaryStr) == n:
				output.add(binaryStr)
				return
			for bit in '01':
				if bit == '1' and len(binaryStr) > 0 and (binaryStr[-1] == '1'):
					return
				else:
					recurBinary(binaryStr + bit)
		recurBinary('')
		return sorted(output)


class Solution:

	def generateBinaryStrings(self, n):

		def generate(l, l1, p, n):
			if len(l1) == n:
				l.append(''.join(l1))
				return
			if p == '1':
				l1.append('0')
				generate(l, l1, '0', n)
				l1.pop()
			else:
				l1.append('0')
				generate(l, l1, '0', n)
				l1.pop()
				l1.append('1')
				generate(l, l1, '1', n)
				l1.pop()
		l = []
		generate(l, [], '', n)
		return l


class Solution:

	def generateBinaryStrings(self, n):
		res = []

		def helper(idx, output):
			if idx >= n:
				res.append(output)
				return
			helper(idx + 1, output + '0')
			if len(output) and output[-1] == '1':
				return
			helper(idx + 1, output + '1')
		helper(0, '')
		return res


class Solution:

	def generateBinaryStrings(self, n):
		from queue import Queue
		q = Queue()
		q.put('')

		def generate(i):
			if i == 0:
				return
			temp_len = q.qsize()
			for j in range(temp_len):
				ele = q.get()
				q.put(ele + '0')
				if len(ele) > 0 and ele[-1] != '1' or len(ele) == 0:
					q.put(ele + '1')
			generate(i - 1)
		generate(n)
		ans = []
		while not q.empty():
			ans.append(q.get())
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		l = []
		self.solve(n, '', 0, l)
		return l

	def solve(self, n, s, index, l):
		if index == n:
			l.append(s)
			return
		elif len(s) == 0:
			self.solve(n, s + '0', index + 1, l)
			self.solve(n, s + '1', index + 1, l)
		elif s[-1] == '0':
			self.solve(n, s + '0', index + 1, l)
			self.solve(n, s + '1', index + 1, l)
		else:
			self.solve(n, s + '0', index + 1, l)


def strings(s, idx, n, l):
	if idx + 1 == n:
		l.append(s)
		return
	if s[idx] == '0':
		strings(s + '0', idx + 1, n, l)
		strings(s + '1', idx + 1, n, l)
	else:
		strings(s + '0', idx + 1, n, l)

class Solution:

	def generateBinaryStrings(self, n):
		l = []
		strings('0', 0, n, l)
		strings('1', 0, n, l)
		return l


class Solution:

	def generateBinaryStrings(self, n):
		return self._generate('', n)

	def _generate(self, prefix, n):
		if len(prefix) == n:
			return [prefix]
		result = self._generate(prefix + '0', n)
		if len(prefix) == 0 or prefix[-1] != '1':
			result += self._generate(prefix + '1', n)
		return result


class Solution:

	def generateBinaryStrings(self, n):

		def binaryStrings(n, lastplace, string, ans):
			if n == 0:
				ans.append(string)
				return
			else:
				binaryStrings(n - 1, 0, string + '0', ans)
				if lastplace == 0:
					binaryStrings(n - 1, 1, string + '1', ans)
		ans = []
		binaryStrings(n, 0, '', ans)
		return ans


class Solution:

	def generateBinaryStrings(self, n):
		ans = []

		def recursive(n, idx=0, curr='', prev=0):
			nonlocal ans
			if idx == n:
				ans.append(curr)
				return
			recursive(n, idx + 1, curr + '0', 0)
			if prev == 0:
				recursive(n, idx + 1, curr + '1', 1)
			return
		recursive(n)
		return ans


class Solution:

	def __init__(self):
		self.binary_subseq = list()

	def generateBinarySubseq(self, n, curr_str):
		if len(curr_str) == n:
			self.binary_subseq.append(curr_str)
			return
		self.generateBinarySubseq(n, curr_str + '0')
		if len(curr_str) > 0 and curr_str[-1] == '1':
			return
		self.generateBinarySubseq(n, curr_str + '1')

	def generateBinaryStrings(self, n):
		self.generateBinarySubseq(n, '')
		return self.binary_subseq


class Solution:

	def generateBinaryStrings(self, n):
		output = []
		self.dfs('', n, output)
		return output

	def dfs(self, path, n, res):
		if len(path) == n:
			res.append(path)
			return
		self.dfs(path + '0', n, res)
		if len(path) and path[-1] == '1':
			return
		self.dfs(path + '1', n, res)


class Solution:

	def recConstruct(self, temp, n, res):
		if len(temp) == n:
			res.append(temp)
			return
		if len(temp) == 0 or temp[-1] == '0':
			self.recConstruct(temp + '0', n, res)
			self.recConstruct(temp + '1', n, res)
		elif temp[-1] == '1':
			self.recConstruct(temp + '0', n, res)

	def generateBinaryStrings(self, n):
		res = []
		self.recConstruct('', n, res)
		return res


class Solution:

	def generateBinaryStrings(self, n):

		def _binary(n):

			def _count(s, ans):
				if len(s) == n:
					ans.append(s)
					return
				if not s or s[-1] == '0':
					_count(s + '1', ans)
				_count(s + '0', ans)
			ans = []
			_count('', ans)
			ans.sort()
			return ans
		return _binary(n)


def solve(ans, res, index, n):
	if index == n:
		ans.append(res)
		return
	if index != 0 and res[index - 1] == '1':
		solve(ans, res + '0', index + 1, n)
	else:
		solve(ans, res + '0', index + 1, n)
		solve(ans, res + '1', index + 1, n)

class Solution:

	def generateBinaryStrings(self, n):
		ans = []
		res = ''
		index = 0
		solve(ans, res, index, n)
		return ans


class Solution:

	def recur(self, n, i, res, s):
		if n == i:
			res.append(s[:])
			return
		self.recur(n, i + 1, res, s + '0')
		if not s or (s and s[-1] != '1'):
			self.recur(n, i + 1, res, s + '1')

	def generateBinaryStrings(self, n):
		res = []
		self.recur(n, 0, res, '')
		return res


class Solution:

	def generateBinaryStrings(self, n):

		def helper(curr):
			if len(curr) == n:
				res.append(curr)
				return
			elif len(curr) == 0:
				helper(curr + '0')
				helper(curr + '1')
			elif curr[-1] == '0':
				helper(curr + '0')
				helper(curr + '1')
			else:
				helper(curr + '0')
		res = []
		curr = ''
		helper(curr)
		return res