Given a positive integer N, the task is to find all the N bit binary numbers having more than or equal 1’s than 0’s for any prefix of the number. 
Example 1:
Input:  N = 2
Output: 11 10
Explanation: 11 and 10 have more than 
or equal 1's than 0's
Example 2:
Input:  N = 3
Output: 111 110 101
Explanation: 111, 110 and 101 have more 
than or equal 1's than 0's
User Task:
Your task is to complete the function NBitBinary() which takes a single number as input and returns the list of strings in decreasing order. You need not take any input or print anything.
Expected Time Complexity: O(|2^{N}|)
Expected Auxiliary Space: O(2^{N})
Constraints:
1 <= N <= 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:

	def NBitBinary(self, N):

		# code here

Solutions:
class Solution:

	def NBitBinary(self, N):
		one = 1
		zero = 0
		op = '1'
		answer = []
		self.Solve(one, zero, op, N - 1, answer)
		return answer

	def Solve(self, one, zero, op, N, answer):
		if N == 0:
			answer.append(op)
			return
		elif one > zero:
			op1 = op + '1'
			op2 = op + '0'
			self.Solve(one + 1, zero, op1, N - 1, answer)
			self.Solve(one, zero + 1, op2, N - 1, answer)
		elif one == zero:
			op = op + '1'
			self.Solve(one + 1, zero, op, N - 1, answer)


class Solution:

	def util(self, n, e, o, s):
		global ans
		if e + o > n:
			return
		if e + o == n:
			ans.append(s)
			return
		if e > o:
			self.util(n, e + 1, o, s + '1')
			self.util(n, e, o + 1, s + '0')
		else:
			self.util(n, e + 1, o, s + '1')

	def NBitBinary(self, N):
		global ans
		ans = []
		self.util(N, 0, 0, '')
		return ans


class Solution:

	def AllNBitBinary(self, N, ones, zeroes, op, res):
		if N == 0:
			res.append(op)
			return
		op1 = op + '1'
		self.AllNBitBinary(N - 1, ones + 1, zeroes, op1, res)
		if ones > zeroes:
			op2 = op + '0'
			self.AllNBitBinary(N - 1, ones, zeroes + 1, op2, res)

	def NBitBinary(self, N):
		res = []
		op = ''
		ones = 0
		zeroes = 0
		self.AllNBitBinary(N, ones, zeroes, op, res)
		return res


class Solution:

	def NBitBinary(self, N):
		ip = n - 1
		op = '1'
		ans = []
		ones = 1
		zeros = 0

		def solve(ip, op, ones, zeros):
			if ip == 0:
				ans.append(op)
				return
			if ones > zeros:
				op1 = op + '1'
				op2 = op + '0'
				ip = ip - 1
				solve(ip, op1, ones + 1, zeros)
				solve(ip, op2, ones, zeros + 1)
			else:
				op1 = op + '1'
				ip = ip - 1
				solve(ip, op1, ones + 1, zeros)
		solve(ip, op, ones, zeros)
		return ans


class Solution:

	def NBitBinary(self, N):
		ans = []
		self.solve(N, 0, 0, '', ans)
		return ans

	def solve(self, n, one, zero, op, ans):
		if n == 0:
			ans.append(op)
			return
		self.solve(n - 1, one + 1, zero, op + '1', ans)
		if one > zero:
			self.solve(n - 1, one, zero + 1, op + '0', ans)


class Solution:

	def NBitBinary(self, N):

		def solve(one, zero, n, op, res):
			if n == 0:
				res.append(op)
				return
			op1 = op
			op1 = op1 + '1'
			solve(one + 1, zero, n - 1, op1, res)
			if one > zero:
				op2 = op
				op2 = op2 + '0'
				solve(one, zero + 1, n - 1, op2, res)
			return
		res = []
		op = ''
		one = 0
		zero = 0
		solve(one, zero, n, op, res)
		return res


class Solution:

	def NBitBinary(self, N):
		ans = []

		def funtoprint(ones, zeros, n, op):
			if n == 0:
				ans.append(op)
				return
			op1 = op
			op1 += '1'
			funtoprint(ones + 1, zeros, n - 1, op1)
			if ones > zeros:
				op2 = op
				op2 += '0'
				funtoprint(ones, zeros + 1, n - 1, op2)
		funtoprint(0, 0, N, '')
		return ans


class Solution:

	def NBitBinary(self, N):
		res = []

		def solve1(op, one, zero, n):
			if one < zero:
				return
			if n == 0:
				res.append(op)
				return
			solve1(op + '1', one + 1, zero, n - 1)
			solve1(op + '0', one, zero + 1, n - 1)
		solve1('', 0, 0, N)
		return res


class Solution:

	def NBitBinary(self, N):
		res = []

		def recur(cur, o, z, n, res):
			if n == 0:
				res.append(cur[:])
				return
			if o == z:
				cur += '1'
				recur(cur, o + 1, z, n - 1, res)
			else:
				cur += '1'
				recur(cur, o + 1, z, n - 1, res)
				cur = cur[:len(cur) - 1] + '0'
				recur(cur, o, z + 1, n - 1, res)
			return
		recur('', 0, 0, N, res)
		return res


class Solution:

	def NBitBinary(self, N):

		def _solve(tmp, bal):
			if len(tmp) == N:
				ans.append(''.join(tmp))
				return
			tmp.append('1')
			_solve(tmp, bal + 1)
			tmp.pop()
			if bal > 0:
				tmp.append('0')
				_solve(tmp, bal - 1)
				tmp.pop()
		(ans, tmp) = ([], [])
		_solve(tmp, 0)
		return ans


class Solution:

	def solve(self, k, N, one, curr):
		if k == N:
			self.ans.append(''.join(curr))
			return
		curr.append('1')
		self.solve(k + 1, N, one + 1, curr)
		curr.pop()
		if one > 0:
			curr.append('0')
			self.solve(k + 1, N, one - 1, curr)
			curr.pop()

	def NBitBinary(self, N):
		self.ans = []
		curr = []
		self.solve(0, N, 0, [])
		return self.ans


class Solution:

	def NBitBinary(self, N):
		op = ''
		count_zero = 0
		count_one = 0
		res = []
		self.solver(op, count_zero, count_one, res, N)
		return res

	def solver(self, op, zero, one, res, N):
		if one + zero == N:
			res.append(op)
			return
		elif one > zero:
			op1 = op + '0'
			op2 = op + '1'
			self.solver(op2, zero, one + 1, res, N)
			self.solver(op1, zero + 1, one, res, N)
		else:
			op += '1'
			self.solver(op, zero, one + 1, res, N)


class Solution:

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

		def rec(zero, one, cur):
			if len(cur) == n:
				res.append(cur)
				return
			rec(zero, one + 1, cur + '1')
			if zero < one:
				rec(zero + 1, one, cur + '0')
		rec(0, 0, '')
		return res


class Solution:

	def NBitBinary(self, N):

		def rec(n, one, zero, curr, res):
			if one + zero == n:
				res.append(curr)
				return
			if one > n:
				return
			rec(n, one + 1, zero, curr + '1', res)
			if one > zero:
				rec(n, one, zero + 1, curr + '0', res)
		res = []
		rec(N, 0, 0, '', res)
		return res


class Solution:

	def NBitBinary(self, N):

		def solve(one, zero, n, st, res):
			if n == 0:
				res.append(st)
				return
			st1 = st
			st1 += '1'
			solve(one + 1, zero, n - 1, st1, res)
			if one > zero:
				st2 = st + '0'
				solve(one, zero + 1, n - 1, st2, res)
			return
		string = ''
		res = []
		solve(0, 0, N, string, res)
		return res


class Solution:

	def NBitBinary(self, N):
		ans = []

		def AllNumber(noOne, noZero, number):
			if noOne + noZero == N:
				ans.append(number)
				return
			if noOne < N:
				AllNumber(noOne + 1, noZero, number + '1')
			if noZero < noOne:
				AllNumber(noOne, noZero + 1, number + '0')
		AllNumber(0, 0, '')
		return ans


class Solution:

	def solve(self, ans, n, o, z, s):
		if o + z == n:
			ans.append(s)
			return
		if o <= n:
			self.solve(ans, n, o + 1, z, s + '1')
		if z < o:
			self.solve(ans, n, o, z + 1, s + '0')

	def NBitBinary(self, N):
		ans = []
		self.solve(ans, N, 0, 0, '')
		return ans


class Solution:

	def NBitBinary(self, N):
		res = []

		def recursive(s, one, zero):
			if one + zero == N:
				if s[0] != '0' and one >= zero:
					res.append(s)
				return
			if one < zero:
				return
			recursive(s + '1', one + 1, zero)
			recursive(s + '0', one, zero + 1)
		recursive('', 0, 0)
		return res


class Solution:

	def NBitBinary(self, N):
		ans = []

		def help(N, c1, c0, str, ans):
			if len(str) == N + 1 and c1 >= c0:
				ans.append(str)
				return ans
			if c1 < c0:
				return
			help(N, c1 + 1, c0, str + '1', ans)
			help(N, c1, c0 + 1, str + '0', ans)
			return ans
		return help(N - 1, 1, 0, '1', ans)


class Solution:

	def NBitBinary(self, N):

		def fun(one, zero, n, op, l):
			if n == 0:
				l.append(op)
				return l
			op1 = op
			op1 = op1 + '1'
			fun(one + 1, zero, n - 1, op1, l)
			if zero < one:
				op2 = op
				op2 = op2 + '0'
				fun(one, zero + 1, n - 1, op2, l)
			return l
		one = 0
		zero = 0
		n = N
		op = ''
		l = []
		return fun(one, zero, n, op, l)


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		out = ''
		sub = []

		def solve(n, ones, zeros, out, sub):
			if n == 0:
				sub.append(out)
				return
			out1 = out
			out1 += '1'
			solve(n - 1, ones + 1, zeros, out1, sub)
			if ones > zeros:
				out2 = out
				out2 += '0'
				solve(n - 1, ones, zeros + 1, out2, sub)
			return
		solve(N, ones, zeros, out, sub)
		return sub


class Solution:

	def NBitBinary(self, N):

		def fun(n_1, n_0, out, res, N):
			if n_1 + n_0 == N:
				res.append(out)
				return res
			if n_1 == n_0:
				n_s = out + '1'
				fun(n_1 + 1, n_0, n_s, res, N)
			elif n_1 > n_0:
				n_s = out + '1'
				n_y = out + '0'
				fun(n_1 + 1, n_0, n_s, res, N)
				fun(n_1, n_0 + 1, n_y, res, N)
		res = []
		out = '1'
		n_1 = 1
		n_0 = 0
		fun(n_1, n_0, out, res, N)
		return res


class Solution:

	def NBitBinary(self, N):
		res = []
		self.generate('', 0, 0, N, res)
		return res[::-1]

	def generate(self, curr, ones, zeros, N, res):
		if len(curr) == N:
			res.append(curr)
			return
		if ones > zeros:
			self.generate(curr + '0', ones, zeros + 1, N, res)
		self.generate(curr + '1', ones + 1, zeros, N, res)


class Solution:

	def NBitBinary(self, N):
		ans = []

		def fun(Z, O, op, N):
			if Z + O == N:
				ans.append(int(op))
				return
			if O > Z:
				fun(Z + 1, O, op + '0', N)
				fun(Z, O + 1, op + '1', N)
			if O == Z:
				fun(Z, O + 1, op + '1', N)
		fun(0, 1, '1', N)
		ans.sort(reverse=True)
		return ans


class Solution:

	def helper(self, blist, one_count, zero_count, N, number):
		if N == 0:
			blist.append(number)
			return
		self.helper(blist, one_count + 1, zero_count, N - 1, number + '1')
		if one_count > zero_count:
			self.helper(blist, one_count, zero_count + 1, N - 1, number + '0')

	def NBitBinary(self, N):
		binary_list = []
		one_count = 0
		zero_count = 0
		number = ''
		self.helper(binary_list, one_count, zero_count, N, number)
		return binary_list


class Solution:

	def NBitBinary(self, N):

		def prefixes(n, z, o, op, a):
			if n == 0:
				a.append(op)
				return
			if z <= o:
				op1 = op + '0'
				op2 = op + '1'
				prefixes(n - 1, z + 1, o, op1, a)
				prefixes(n - 1, z, o + 1, op2, a)
			else:
				op1 = op + '1'
				prefixes(n - 1, z, o + 1, op1, a)
		a = []
		prefixes(N - 1, 0, 0, '1', a)
		a.sort(reverse=True)
		return a


def N_bit(N, ind, on, ze, st, res):
	if ze > on:
		return
	if ind >= N:
		res.append(st)
		return
	N_bit(N, ind + 1, on + 1, ze, st + '1', res)
	N_bit(N, ind + 1, on, ze + 1, st + '0', res)

class Solution:

	def NBitBinary(self, N):
		res = []
		st = ''
		ind = 0
		on = 0
		ze = 0
		N_bit(N, ind, on, ze, st, res)
		return res


class Solution:

	def NBitBinary(self, N):

		def solve(ans, N, op, o, z):
			if len(op) == N:
				ans.append(''.join(op))
				return
			if o == z:
				op.append('1')
				solve(ans, N, op, o + 1, z)
			elif o > z:
				(op1, op2) = (op.copy(), op.copy())
				op1.append('1')
				solve(ans, N, op1, o + 1, z)
				op2.append('0')
				solve(ans, N, op2, o, z + 1)
		ans = []
		(op, o, z) = ([], 0, 0)
		solve(ans, N, op, o, z)
		return ans


class Solution:

	def NBitBinary(self, N):
		return sorted(self.helper(N - 1, set([('1', 1)])), reverse=True)

	def helper(self, n, setti):
		if n == 0:
			return [item[0] for item in setti]
		temp = set()
		for item in setti:
			temp.add((item[0] + '1', item[1] + 1))
			if item[1] > 0:
				temp.add((item[0] + '0', item[1] - 1))
		return self.helper(n - 1, temp)


class Solution:

	def NBitBinary(self, N):

		def helperFunction(one_count, zero_count, generated_string):
			if len(generated_string) == N:
				return [generated_string]
			result = []
			if one_count == zero_count:
				choice_1 = helperFunction(one_count + 1, zero_count, generated_string + '1')
				result.extend(choice_1)
			elif one_count < N and zero_count < N and (one_count > zero_count):
				choice_1 = helperFunction(one_count + 1, zero_count, generated_string + '1')
				choice_2 = helperFunction(one_count, zero_count + 1, generated_string + '0')
				result.extend(choice_1)
				result.extend(choice_2)
			return result
		answer = helperFunction(0, 0, '')
		return answer


class Solution:

	def NBitBinary(self, N):
		res = []

		def solve(outp: str):
			if len(outp) == N:
				res.append(outp)
				return
			op1 = outp
			op1 += '1'
			c1 = outp.count('1')
			c0 = outp.count('0')
			solve(op1)
			if c1 > c0:
				op2 = outp
				op2 += '0'
				solve(op2)
		solve('1')
		return res


class Solution:

	def NBitBinary(self, N):
		res = []

		def helper(ones, zero, n, op):
			if n == 0:
				res.append(op)
				return
			helper(ones + 1, zero, n - 1, op + '1')
			if ones > zero:
				helper(ones, zero + 1, n - 1, op + '0')
		helper(0, 0, N, '')
		return res


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		output = ''
		outlist = []

		def solve(N, ones, zeros, output):
			if N == 0:
				outlist.append(output)
				return
			out1 = output
			out1 += '1'
			solve(N - 1, ones + 1, zeros, out1)
			if ones > zeros:
				out2 = output
				out2 += '0'
				solve(N - 1, ones, zeros + 1, out2)
		solve(N, ones, zeros, output)
		return outlist


class Solution:

	def NBitBinary(self, N):
		sol = []

		def backtrack(curr, ones, zeros):
			if len(curr) == N:
				sol.append(''.join(curr))
				return
			curr.append('1')
			backtrack(curr, ones + 1, zeros)
			curr.pop()
			if zeros < ones:
				curr.append('0')
				backtrack(curr, ones, zeros + 1)
				curr.pop()
		backtrack([], 0, 0)
		return sol


class Solution:

	def NBitBinary(self, N):
		v = []
		op = ''
		one = 0
		zero = 0

		def solve(one, zero, N, op):
			if N == 0:
				v.append(op)
				return
			op1 = op + '1'
			solve(one + 1, zero, N - 1, op1)
			if one > zero:
				op2 = op + '0'
				solve(one, zero + 1, N - 1, op2)
			return
		solve(one, zero, N, op)
		v.sort(reverse=True)
		return v


class Solution:

	def NBitBinary(self, N):

		def helper(n, one, zero, op, res):
			if n == 0:
				res.append(op)
				return
			if one > zero:
				helper(n - 1, one + 1, zero, op + '1', res)
				helper(n - 1, one, zero + 1, op + '0', res)
			else:
				helper(n - 1, one + 1, zero, op + '1', res)
		res = list()
		helper(N, 0, 0, str(), res)
		return res


class Solution:

	def NBitBinary(self, N):
		output = ''
		ls = []

		def slove(output, one, zero, n):
			if n == 0:
				ls.append(output)
				return
			if one != 0:
				slove(output + '1', one - 1, zero, n - 1)
			if zero > one:
				slove(output + '0', one, zero - 1, n - 1)
		slove(output, N, N, N)
		return ls


class Solution:

	def solve(self, inp, out, zero, one, arr):
		if inp == 0:
			arr.append(out)
			return arr
		if zero == one:
			out += '1'
			arr = self.solve(inp - 1, out, zero, one + 1, arr)
			return arr
		out1 = out + '0'
		out2 = out + '1'
		arr = self.solve(inp - 1, out1, zero + 1, one, arr)
		arr = self.solve(inp - 1, out2, zero, one + 1, arr)
		return arr

	def NBitBinary(self, N):
		arr = self.solve(N, '', 0, 0, [])
		arr.sort(reverse=True)
		return arr


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		N = N
		ans = []
		return self.solve(N, ones, zeros, '', ans)

	def solve(self, N, ones, zeros, op, ans):
		if ones + zeros == N:
			ans.append(op)
			return ans
		if ones > zeros:
			op1 = op
			op2 = op
			op1 = op1 + '1'
			op2 = op2 + '0'
			ans = self.solve(N, ones + 1, zeros, op1, ans)
			ans = self.solve(N, ones, zeros + 1, op2, ans)
		elif ones == zeros:
			op1 = op
			op1 = op1 + '1'
			ans = self.solve(N, ones + 1, zeros, op1, ans)
		return ans


class Solution:

	def NBitBinary(self, N):
		ans = []

		def helper(N, num, count_ones, count_zeroes):
			if N == 0:
				ans.append(int(num))
				return
			helper(N - 1, num + '1', count_ones + 1, count_zeroes)
			if count_ones > count_zeroes:
				helper(N - 1, num + '0', count_ones, count_zeroes + 1)
		helper(N, '', 0, 0)
		return ans


class Solution:

	def NBitBinary(self, N):

		def solve(one, zero, N, op, vec):
			if N == 0:
				vec.append(''.join(op))
				return
			op1 = op[:]
			op1.append('1')
			solve(one + 1, zero, N - 1, op1[:], vec)
			if one > zero:
				op2 = op[:]
				op2.append('0')
				solve(one, zero + 1, N - 1, op2[:], vec)
		op = []
		one = 0
		zero = 0
		vec = []
		solve(one, zero, N, op, vec)
		return vec


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		ans = []
		self.NBitBinaryHelper('', ones, zeros, N, ans)
		ans.sort(reverse=True)
		return ans

	def NBitBinaryHelper(self, s, ones, zeros, n, ans):
		if ones + zeros == n:
			if s[0] == '1' and ones >= zeros:
				ans.append(s)
			return
		if ones < zeros:
			return
		self.NBitBinaryHelper(s + '1', ones + 1, zeros, n, ans)
		self.NBitBinaryHelper(s + '0', ones, zeros + 1, n, ans)


class Solution:

	def NBitBinary(self, N):

		def solver(n, temp, count1, count2, ind):
			if ind >= n:
				ans.append(temp)
				return
			if count1 < n:
				solver(n, temp + '1', count1 + 1, count2, ind + 1)
			if count2 < count1:
				solver(n, temp + '0', count1, count2 + 1, ind + 1)
		ans = []
		solver(n, '', 0, 0, 0)
		return ans


class Solution:

	def NBitBinary(self, N):

		def printer(num, extra, remain):
			if remain == 0:
				ans.append(num)
				return
			printer(num + '1', extra + 1, remain - 1)
			if extra > 0:
				printer(num + '0', extra - 1, remain - 1)
		strr = ''
		ans = []
		printer(strr, 0, N)
		return ans


class Solution:

	def NBitBinary(self, N):
		ones = 1
		zeros = 0
		op = '1'
		result = []
		self.NBitBinary2(N - 1, ones, zeros, op, result)
		return result

	def NBitBinary2(self, N, ones, zeros, op, result):
		if N == 0:
			result.append(op)
			return
		op1 = op + '1'
		self.NBitBinary2(N - 1, ones + 1, zeros, op1, result)
		if ones > zeros:
			op1 = op + '0'
			self.NBitBinary2(N - 1, ones, zeros + 1, op1, result)
		return


class Solution:

	def NBitBinary(self, n):
		count0 = 1
		count1 = 0
		op = '1'
		ans = []
		self.logic(n - 1, count0, count1, op, ans)
		return ans

	def logic(self, n, count1, count0, op, ans):
		if n == 0:
			ans.append(op)
			return
		if count1 >= count0:
			op1 = op
			op1 += '1'
			self.logic(n - 1, count1 + 1, count0, op1, ans)
		if count0 < count1:
			op2 = op
			op2 += '0'
			self.logic(n - 1, count1, count0 + 1, op2, ans)


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		ans = []

		def helper(output, ones, zeros):
			if len(output) == N:
				ans.append(output)
			elif ones <= zeros:
				helper(output + '1', ones + 1, zeros)
			elif ones > zeros:
				helper(output + '1', ones + 1, zeros)
				helper(output + '0', ones, zeros + 1)
		helper('', 0, 0)
		return ans


class Solution:

	def NBitBinary(self, N):
		frontier = [['1', 1, 0]]
		lvl = 1
		while lvl < N:
			nxt = []
			for i in frontier:
				nxt.append([i[0] + '1', i[1] + 1, i[2]])
				if i[2] + 1 <= i[1]:
					nxt.append([i[0] + '0', i[1], i[2] + 1])
			frontier = nxt
			lvl += 1
		a = [i[0] for i in frontier]
		return a


class Solution:

	def calculateSum(self, n):
		s = 0
		for i in n:
			s += int(i)
		return s

	def NBitBinary(self, N):
		frontier = [['1', 1, 0]]
		lvl = 1
		while lvl < N:
			nxt = []
			for i in frontier:
				nxt.append([i[0] + '1', i[1] + 1, i[2]])
				if i[2] + 1 <= i[1]:
					nxt.append([i[0] + '0', i[1], i[2] + 1])
			frontier = nxt
			lvl += 1
		a = [i[0] for i in frontier]
		return a


class Solution:

	def NBitBinary(self, N):
		result = []

		def binary(s1, a, b):
			if len(s1) == N:
				result.append(s1)
				return
			binary(s1 + '1', a + 1, b)
			if b < a:
				binary(s1 + '0', a, b + 1)
		binary('', 0, 0)
		return result


class Solution:

	def NBitBinary(self, N):
		ans = []

		def print_binary(n, o, z, output):
			if n == 0:
				if o >= z:
					ans.append(output)
				return
			print_binary(n - 1, o + 1, z, ''.join([output, '1']))
			if z < o:
				print_binary(n - 1, o, z + 1, ''.join([output, '0']))
		print_binary(N, 0, 0, '')
		return ans


class Solution:

	def NBitBinary(self, N):

		def recurse(ones, zeros, n, res):
			if n == 0:
				output.append(res[:])
				return
			if n > 0:
				op1 = res + '1'
				recurse(ones + 1, zeros, n - 1, op1)
			if ones > zeros:
				op2 = res + '0'
				recurse(ones, zeros + 1, n - 1, op2)
		output = []
		recurse(0, 0, N, '')
		return output


class Solution:

	def NBitBinary(self, N):
		req = []

		def recursion(zeroes, ones, N, op):
			if N == 0:
				req.append(op)
				return
			op1 = op + '1'
			recursion(zeroes, ones + 1, N - 1, op1)
			if ones > zeroes:
				op2 = op + '0'
				recursion(zeroes + 1, ones, N - 1, op2)
		recursion(0, 0, N, '')
		return req


class Solution:

	def solve(self, res, ones, zeros, n, arr):
		if n == 0:
			arr.append(res)
			return
		if ones == zeros:
			self.solve(res + '1', ones + 1, zeros, n - 1, arr)
		else:
			self.solve(res + '1', ones + 1, zeros, n - 1, arr)
			self.solve(res + '0', ones, zeros + 1, n - 1, arr)

	def NBitBinary(self, N):
		arr = []
		self.solve('', 0, 0, N, arr)
		return arr


class Solution:

	def NBitBinary(self, N):

		def helper(zero, one, li, n, output):
			if n == 0:
				li.append(output)
				return
			if one > zero:
				output2 = output + '1'
				helper(zero, one + 1, li, n - 1, output2)
				output1 = output + '0'
				helper(zero + 1, one, li, n - 1, output1)
			else:
				output += '1'
				helper(zero, one + 1, li, n - 1, output)
		li = []
		helper(0, 0, li, N, '')
		return li


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		op = ''
		result = []

		def solve(ones, zeros, op, n):
			if n == 0:
				result.append(op)
				return
			op1 = op
			op1 = op1 + '1'
			solve(ones + 1, zeros, op1, n - 1)
			if ones > zeros:
				op2 = op
				op2 = op2 + '0'
				solve(ones, zeros + 1, op2, n - 1)
			return
		solve(ones, zeros, op, N)
		return result


class Solution:

	def NBitBinary(self, N):
		s = ''
		arr = []

		def generate_bin(s, n, arr):
			if n == 0:
				arr.append(s)
				return
			if s.count('1') > s.count('0'):
				s1 = s + '0'
				s2 = s + '1'
				generate_bin(s2, n - 1, arr)
				generate_bin(s1, n - 1, arr)
			if s.count('1') == s.count('0'):
				generate_bin(s + '1', n - 1, arr)
			return arr
		return generate_bin(s, N, arr)


class Solution:

	def NBitBinary(self, N):
		ans = []
		ones = zeros = 0
		op = ''

		def generate(N, ones, zeros, op):
			if N == 0:
				ans.append(op)
				return
			generate(N - 1, ones + 1, zeros, op + '1')
			if ones > zeros:
				generate(N - 1, ones, zeros + 1, op + '0')
		generate(N, ones, zeros, op)
		return ans


class Solution:

	def NBitBinary(self, N):
		ones = 0
		zeros = 0
		n = N
		res = ''
		ans = []

		def solve(res, ones, zeros, n):
			if n == 0:
				ans.append(res)
				return
			elif ones == zeros:
				res1 = res + '1'
				ones3 = ones - 1
				solve(res1, ones3, zeros, n - 1)
			else:
				res1 = res + '1'
				ones1 = ones - 1
				n1 = n - 1
				solve(res1, ones1, zeros, n1)
				res2 = res + '0'
				zeros1 = zeros - 1
				n2 = n - 1
				solve(res2, ones, zeros1, n2)
		solve(res, ones, zeros, n)
		return ans


class Solution:

	def solve(self, i, N, on, ze, ans, lst=''):
		if i == N:
			ans.append(lst)
			return
		if on < N:
			lst += '1'
			self.solve(i + 1, N, on + 1, ze, ans, lst)
			lst = lst[:len(lst) - 1]
		if ze < on:
			lst += '0'
			self.solve(i + 1, N, on, ze + 1, ans, lst)
			lst = lst[:len(lst) - 1]

	def NBitBinary(self, N):
		ans = []
		self.solve(0, N, 0, 0, ans)
		return ans


class Solution:

	def NBitBinary(self, N):
		ans = []

		def generate(n, no_of_ones, no_of_zeros, op: str):
			if no_of_ones + no_of_zeros == n:
				ans.append(op)
				return
			if no_of_ones == no_of_zeros:
				op += '1'
				new_ones = no_of_ones + 1
				generate(n, new_ones, no_of_zeros, op)
			elif no_of_ones > no_of_zeros:
				op1 = op + '1'
				new_ones = no_of_ones + 1
				generate(n, new_ones, no_of_zeros, op1)
				op2 = op + '0'
				new_zeros = no_of_zeros + 1
				generate(n, no_of_ones, new_zeros, op2)
		op = ''
		generate(N, 0, 0, op)
		return ans


class Solution:

	def NBitBinary(self, N):
		res = []

		def recur(ones, zeros, cur):
			if ones > N:
				return
			if len(cur) == N:
				res.append(cur)
				return
			recur(ones + 1, zeros, cur + '1')
			if ones > zeros:
				recur(ones, zeros + 1, cur + '0')
		recur(0, 0, '')
		return res


class Solution:

	def NBitBinary(self, N):

		def Nbit(ones, zeros, n, res, out):
			if n == 0:
				res.append(out)
				return
			if ones >= 0:
				out1 = out
				out1 = out1 + '1'
				Nbit(ones + 1, zeros, n - 1, res, out1)
			if zeros < ones:
				out2 = out
				out2 = out2 + '0'
				Nbit(ones, zeros + 1, n - 1, res, out2)
			return
		ones = 0
		zeros = 0
		res = []
		out = ''
		Nbit(ones, zeros, N, res, out)
		return res


class Solution:

	def NBitBinary(self, N):
		op = ''
		lis = []
		one = 0
		zero = 0

		def solve(N, one, zero, op, lis):
			if N == 0:
				lis.append(op)
				return
			if one == zero:
				op += '1'
				solve(N - 1, one + 1, zero, op, lis)
			else:
				op1 = op
				op2 = op
				op1 += '1'
				op2 += '0'
				solve(N - 1, one + 1, zero, op1, lis)
				solve(N - 1, one, zero + 1, op2, lis)
		solve(N, one, zero, op, lis)
		return lis


class Solution:

	def NBitBinary(self, N):
		res = []

		def recur(i, N, s, c0, c1):
			if i == N:
				res.append(s)
				return
			recur(i + 1, N, s + '1', c0, c1 + 1)
			if c0 < c1:
				recur(i + 1, N, s + '0', c0 + 1, c1)
		recur(1, N, '1', 0, 1)
		return res


class Solution:

	def NBitBinary(self, N):
		ip = N
		op = ''
		one = 0
		zero = 0
		l = []
		ans = self.solve(ip, op, one, zero, l)
		return ans

	def solve(self, ip, op, one, zero, l):
		if ip == 0:
			l.append(op)
			return
		else:
			op1 = op
			op1 += '1'
			self.solve(ip - 1, op1, one + 1, zero, l)
			if one > zero:
				op2 = op
				op2 += '0'
				self.solve(ip - 1, op2, one, zero + 1, l)
			return l


class Solution:

	def NBitBinary(self, N):
		ans = []

		def fun(one, zero, n, curr):
			if one + zero == n:
				if zero <= one:
					ans.append(curr)
			elif one <= zero and one + zero < n:
				fun(one + 1, zero, n, curr + '1')
			elif one > zero and one + zero < n:
				fun(one + 1, zero, n, curr + '1')
				fun(one, zero + 1, n, curr + '0')
			elif one + zero > n:
				return
		fun(0, 0, N, '')
		return ans


class Solution:

	def NBitBinary(self, N):
		ans = []
		ans = self.solve('1', ans, N, 1, 0)
		return ans

	def solve(self, op, ans, N, ones, zeros):
		if len(op) == N:
			ans.append(op)
			return ans
		if ones == zeros:
			self.solve(op + '1', ans, N, ones + 1, zeros)
		else:
			self.solve(op + '1', ans, N, ones + 1, zeros)
			self.solve(op + '0', ans, N, ones, zeros + 1)
		return ans


class Solution:

	def NBitBinary(self, N):
		res = []
		op = '1'
		ones = 1
		zeros = 0

		def helper(N, ones, zeros, res, op):
			if N == 0:
				if ones >= zeros:
					res.append(op)
				return
			if ones == zeros:
				helper(N - 1, ones + 1, zeros, res, op + '1')
				return
			op1 = op + '0'
			op2 = op + '1'
			helper(N - 1, ones, zeros + 1, res, op1)
			helper(N - 1, ones + 1, zeros, res, op2)
			return
		helper(N - 1, ones, zeros, res, op)
		res.sort(reverse=True, key=lambda x: int(x, 2))
		return res


class Solution:

	def solve(self, n, i, ans, out):
		if n == 0:
			ans.append(out)
			return
		self.solve(n - 1, i + 1, ans, out + '1')
		if i > 0:
			self.solve(n - 1, i - 1, ans, out + '0')

	def NBitBinary(self, N):
		i = 0
		ans = []
		out = ''
		self.solve(n, i, ans, out)
		return ans


class Solution:

	def NBitBinary(self, N):
		res = []

		def isonegreater(bins):
			countO = 0
			countI = 0
			for el in bins:
				if el == '1':
					countI += 1
				elif el == '0':
					countO += 1
				if countI < countO:
					return False
			return True
		if N == 0:
			return []
		for i in range(2 ** (N - 1), 2 ** N):
			binar = str(bin(i)).lstrip('0b')
			if isonegreater(binar):
				res.append(binar)
		res.sort(reverse=True)
		return res


class Solution:

	def NBitBinary(self, N):
		s = '1'
		i = 0
		one = 1
		zero = 0
		ans = []

		def fun(i, one, zero, s):
			if i == N - 1:
				ans.append(s)
				return
			if one >= zero:
				pick1 = s + '1'
				fun(i + 1, one + 1, zero, pick1)
			if one > zero:
				pick2 = s + '0'
				fun(i + 1, one, zero + 1, pick2)
		fun(i, one, zero, s)
		return ans


def solve(output, one, zero, n, li):
	if n == 0:
		li.append(output)
		return
	if one > zero:
		solve(output + '1', one + 1, zero, n - 1, li)
		solve(output + '0', one, zero + 1, n - 1, li)
	else:
		solve(output + '1', one + 1, zero, n - 1, li)

class Solution:

	def NBitBinary(self, N):
		li = []
		solve('', 0, 0, N, li)
		return li


class Solution:

	def NBitBinary(self, N):
		out = 1
		o = 1
		z = 0
		li = []

		def binary(out, o, z):
			if z > o:
				return
			if o + z == N:
				li.append(out)
				return
			op1 = out * 10 + 1
			op2 = out * 10
			binary(op1, o + 1, z)
			binary(op2, o, z + 1)
		binary(out, o, z)
		return li