Given an integer N, print all the N digit numbers in increasing order, such that their digits are in strictly increasing order(from left to right).
Example 1:
Input:
N = 1
Output:
0 1 2 3 4 5 6 7 8 9
Explanation:
Single digit numbers are considered to be 
strictly increasing order.
Example 2:
Input:
N = 2
Output:
12 13 14 15 16 17 18 19 23....79 89
Explanation:
For N = 2, the correct sequence is
12 13 14 15 16 17 18 19 23 and so on 
up to 89.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function increasingNumbers() which takes an integer N as an input parameter and return the list of numbers such that their digits are in strictly increasing order.
Expected Time Complexity: O(9^{N})
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def increasingNumbers(self, N):

    	#code here

Solutions:
class Solution:

	def solve(self, k, n, curr, prev=0):
		if k == n:
			self.ans.append(curr)
			return
		for i in range(prev + 1, 10):
			curr = curr * 10 + i
			self.solve(k + 1, n, curr, i)
			curr = curr // 10

	def increasingNumbers(self, N):
		self.ans = [] if N != 1 else [0]
		self.solve(0, N, 0)
		return self.ans


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			ans.append(0)

		def help(x, n, num, ans):
			if n == 0:
				ans.append(num)
				return
			for i in range(x, 10):
				a = num * 10 + i
				help(i + 1, n - 1, a, ans)
		help(1, N, 0, ans)
		return ans


class Solution:

	def solve(self, last, n, num):
		if n == 0:
			self.ans.append(num)
			return
		for i in range(last, 10):
			a = num * 10 + i
			self.solve(i + 1, n - 1, a)

	def increasingNumbers(self, N):
		res = []
		for i in range(10):
			res.append(i)
		if N == 1:
			return res
		self.ans = []
		self.solve(1, N, 0)
		return self.ans


class Solution:

	def increasingNumbers(self, N):

		def rec(lis, lowlimit, n, num, loopcount):
			if n == 1 and loopcount == 0:
				lis.append(0)
			if loopcount == n:
				lis.append(num)
				return
			for i in range(lowlimit, 10):
				rec(lis, i + 1, n, num * 10 + i, loopcount + 1)
			return lis
		return rec([], 1, N, 0, 0)


class Solution:

	def solve(self, start, num, n, ans):
		if n == 0:
			ans.append(num)
			return
		for i in range(start, 10):
			curNum = num * 10 + i
			self.solve(i + 1, curNum, n - 1, ans)

	def increasingNumbers(self, n):
		ans = []
		if n == 1:
			for i in range(10):
				ans.append(i)
			return ans
		self.solve(1, 0, n, ans)
		return ans


class Solution:

	def increasingNumbers(self, N, curr=0, al=None):
		if al == None and N == 1:
			return [*range(10)]
		if N == 1:
			return map(str, range(curr + 1, 10))
		ans = []
		for x in range(curr + 1, 10):
			for y in self.increasingNumbers(N - 1, x, al=1):
				ans.append(str(x) + y)
		return ans


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return [i for i in range(0, 10)]
		return self.solve(N, 0, 0)

	def solve(self, n, ans, i):
		if n == 0:
			return [ans]
		res = []
		for i in range(i + 1, 10):
			res.extend(self.solve(n - 1, ans * 10 + i, i))
		return res


class Solution:

	def increasingNumbers(self, N):
		res = []
		if N == 1:
			res.append(0)

		def rec(s, j):
			if len(s) == N:
				res.append(int(s))
				return
			for i in range(j, 10):
				if len(s) > 0 and i > int(s[-1]):
					rec(s + str(i), i + 1)
				elif len(s) == 0:
					rec(str(i), i + 1)
				else:
					rec(s, i + 1)
		rec('', 1)
		return res


class Solution:
	l = []

	def fun(self, n, le, r):
		if le == r:
			self.l.append(n)
			return
		for i in range(n % 10 + 1, 10):
			self.fun(n * 10 + i, le + 1, r)

	def increasingNumbers(self, N):
		self.l = []
		self.fun(0, 0, N)
		if N == 1:
			self.l.insert(0, 0)
		return self.l


class Solution:
	l = []

	def rec(self, n, temp, par):
		if n > 10 ** (temp - 1):
			return
		x = n % 10
		for i in range(x + 1, 10, 1):
			if par == temp:
				self.l.append(n * 10 + i)
			self.rec(n * 10 + i, temp, par + 1)

	def increasingNumbers(self, n):
		self.l = []
		self.rec(0, n, 1)
		if n == 1:
			self.l.insert(0, 0)
		return self.l


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 0:
			return ans
		else:
			if N == 1:
				ans.append(0)

			def add_digit(s, last):
				if len(s) == N:
					ans.append(int(s))
				else:
					for digit in range(last + 1, 11 - N + len(s)):
						add_digit(s + str(digit), digit)
			add_digit('', 0)
			return ans


class Solution:

	def increasingNumbers(self, N):
		n_one = [i for i in range(10)]
		if N == 1:
			return n_one
		ans = []
		temp = n_one.copy()
		for i in range(1, N):
			arr = []
			for digit in temp:
				if digit == 0:
					continue
				n = digit % 10 + 1
				for j in range(n, 10):
					arr.append(digit * 10 + j)
			if i == N - 1:
				ans.extend(arr.copy())
			temp = arr.copy()
		return ans


class Solution:

	def increasingNumbers(self, n):
		l = [0] if n == 1 else []
		lower = 0
		upper = 0
		for i in range(1, n + 1):
			lower += i * 10 ** (n - i)
			upper += (10 - n + i - 1) * 10 ** (n - i)

		def add_ones(num):
			if num > upper:
				return 0
			if num not in l:
				l.append(num)
				for i in range(1, n + 1):
					if num % 10 != 9:
						new_num = num + int('1' * i)
						add_ones(new_num)
		add_ones(lower)
		l.sort()
		return l


class Solution:

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

		def solve(n, first, data):
			if n == 0:
				res.append(data)
			for i in range(first + 1, 10):
				solve(n - 1, i, data * 10 + i)
		for i in range(10):
			if i == 0 and N != 1:
				continue
			solve(N - 1, i, i)
		return res


class Solution:

	def solve(self, N, lst, ans, prev):
		if len(lst) == N:
			ans.append(int(lst))
			return
		for i in range(prev + 1, 10):
			lst += str(i)
			self.solve(N, lst, ans, i)
			lst = lst[:len(lst) - 1]

	def increasingNumbers(self, N):
		if N == 1:
			ans = [i for i in range(10)]
			return ans
		ans = []
		self.solve(N, '', ans, 0)
		return ans


class Solution:

	def perm(self, m, c, N, l, t):
		if len(t) == N:
			m.append(t)
			return
		for j in range(c, 9):
			self.perm(m, j + 1, N, l, t + l[j])

	def increasingNumbers(self, N):
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		l = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
		c = 0
		m = []
		self.perm(m, c, N, l, '')
		return m


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return [num for num in range(0, 10)]
		result = []
		for i in range(1, 10):
			self._increasingNumbers(i, 1, N, result)
		return result

	def _increasingNumbers(self, currNum, currSize, size, res):
		if currSize == size:
			res.append(currNum)
			return
		lastDigit = currNum % 10
		for i in range(lastDigit + 1, 10):
			newCurrNum = currNum * 10 + i
			self._increasingNumbers(newCurrNum, currSize + 1, size, res)


class Solution:

	def solve(self, st, N, ans, s):
		if len(s) == N:
			ans.append(int(s))
			return
		for i in range(st, 10):
			s = s + str(i)
			self.solve(i + 1, N, ans, s)
			s = s[:-1]

	def increasingNumbers(self, N):
		if N == 1:
			return [x for x in range(0, 10)]
		ans = []
		s = ''
		st = 1
		self.solve(st, N, ans, s)
		return ans


class Solution:

	def increasingNumbers(self, N):

		def f(N, n, temp, ans):
			if n == N:
				ans += [int(temp)]
			last = int(temp[-1])
			for j in range(last + 1, 10):
				f(N, n + 1, temp + str(j), ans)
		if N == 1:
			return [i for i in range(10)]
		else:
			ans = []
			for i in range(1, 10):
				f(N, 1, str(i), ans)
			return ans


def dfs(s, n, sb, ans):
	if len(sb) >= n:
		return ans.append(int(sb))
	for i in range(s, 10):
		sb += str(i)
		dfs(i + 1, n, sb, ans)
		sb = sb.replace(sb[len(sb) - 1], '')
	return ans

class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			dfs(0, N, '', ans)
		else:
			dfs(1, N, '', ans)
		return ans


class Solution:

	def increasingNumbers(self, N):

		def re(a, n, s, k):
			if len(s) == n:
				k.append(s)
				return
			for i in range(len(a)):
				if s == '':
					s = s + str(a[i])
					re(a, n, s, k)
					s = s[:len(s) - 1]
				elif a[i] > int(s[-1]) and s[-1] != '0':
					s = s + str(a[i])
					re(a, n, s, k)
					s = s[:len(s) - 1]
		a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		s = ''
		k = []
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		re(a, N, s, k)
		return k


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			for i in range(10):
				ans.append(i)
			return ans

		def solution(temp, n, ind):
			if n == 0:
				ans.append(int(temp))
				return
			for i in range(ind, 10):
				solution(temp + str(i), n - 1, i + 1)
		solution('', N, 1)
		return ans


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			ans.append(0)

		def helper(s, last):
			if len(s) == N:
				ans.append(int(s))
			else:
				for i in range(last + 1, 11 - N + len(s)):
					helper(s + str(i), i)
		helper('', 0)
		return ans


class Solution:

	def increasingNumbers(self, N):

		def rec(curr, sum, N, res):
			if N == 0:
				res.append(sum)
				return
			for i in range(curr, 10):
				a = sum * 10 + i
				rec(i + 1, a, N - 1, res)
		res = []
		if N == 1:
			for i in range(10):
				res.append(i)
			return res
		else:
			rec(1, 0, N, res)
			return res


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def increasingNumbers(self, N):

		def rec(current, N, s, res, i):
			if i == N:
				res.append(s)
				return
			for j in range(current, 10):
				temp = s * 10 + j
				rec(j + 1, N, temp, res, i + 1)
		res = []
		if N == 1:
			for i in range(10):
				res.append(i)
			return res
		rec(1, N, 0, res, 0)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.increasingNumbers(N)
		for num in ans:
			print(num, end=' ')
		print()


class Solution:

	def increasingNumbers(self, N):

		def rec(curr, N, sum, res):
			if N == 0:
				res.append(sum)
				return
			for i in range(curr, 10):
				a = 10 * sum + i
				rec(i + 1, N - 1, a, res)
		res = []
		if N == 1:
			for i in range(10):
				res.append(i)
			return res
		else:
			rec(1, N, 0, res)
			return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.increasingNumbers(N)
		for num in ans:
			print(num, end=' ')
		print()


class Solution:

	def increasingNumbers(self, N):

		def rec(last, count, num, lis):
			if count == 0:
				lis.append(num)
				return
			for i in range(last, 10):
				n = num * 10 + i
				rec(i + 1, count - 1, n, lis)
		if N == 1:
			return [i for i in range(10)]
		lis = []
		rec(1, N, 0, lis)
		return lis
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.increasingNumbers(N)
		for num in ans:
			print(num, end=' ')
		print()


import sys

class Solution:

	def increasingNumbers(self, N):

		def rec(current, N, sum, res):
			if N == 0:
				res.append(sum)
				return
			for i in range(current, 10):
				a = sum * 10 + i
				rec(i + 1, N - 1, a, res)
		res = []
		if N == 1:
			for i in range(10):
				res.append(i)
			return res
		else:
			rec(1, N, 0, res)
			return res


class Solution:

	def increasingNumbers(self, N):
		lst = [i for i in range(1, 10)]

		def incrNum(n, s, lst, ans):
			if n == 0:
				ans.append(s)
				return
			for num in lst:
				if s % 10 < num:
					incrNum(n - 1, s * 10 + num, lst, ans)
		ans = []
		if N == 1:
			ans.append(0)
		incrNum(N, 0, lst, ans)
		return ans


class Solution:

	def increasingNumbers(self, N):
		x = []
		if N == 1:
			x.append(0)

		def func(a, b='0', ch=''):
			if a == 0:
				x.append(int(ch))
				return
			for i in range(ord(b) + 1, ord('9') + 1):
				func(a - 1, chr(i), ch + chr(i))
			return x
		return func(N)


def increasingdigit(start, st, n, arr):
	if n == 0:
		arr.append(int(st))
		return
	for i in range(start, 10):
		increasingdigit(i + 1, st + str(i), n - 1, arr)

class Solution:

	def increasingNumbers(self, N):
		arr = []
		if N == 1:
			arr.append(0)
		increasingdigit(1, '', N, arr)
		return arr


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			for i in range(0, 10):
				ans.append(i)
			return ans
		self.solve(1, '', N, ans)
		return ans

	def solve(self, start, out, n, ans):
		if n == 0:
			ans.append(out)
			return
		for i in range(start, 10):
			str1 = out + str(i)
			self.solve(i + 1, str1, n - 1, ans)


class Solution:

	def __init__(self):
		self.ans = []

	def recursiveNumbers(self, last, N, num):
		if N == 0:
			self.ans.append(num)
			return
		for i in range(last, 10):
			curr_num = num * 10 + i
			self.recursiveNumbers(i + 1, N - 1, curr_num)

	def increasingNumbers(self, N):
		if N == 1:
			for i in range(0, 10):
				self.ans.append(i)
			return self.ans
		self.recursiveNumbers(1, N, 0)
		return self.ans


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		res = []
		self.helper(N, '', res)
		return res

	def helper(self, n, ans, res):
		if n == 0:
			res.append(int(ans))
			return
		for i in range(1, 10):
			if len(ans) > 0:
				if ans[-1] < str(i):
					ans += str(i)
					self.helper(n - 1, ans, res)
					ans = ans[:len(ans) - 1]
			else:
				ans += str(i)
				self.helper(n - 1, ans, res)
				ans = ans[:len(ans) - 1]


class Solution:

	def increasingNumbers(self, N):
		l = []

		def f(dig, last):
			if len(dig) == N:
				if not (len(dig) > 1 and dig[0] == '0'):
					l.append(dig)
			for i in range(last + 1, 10):
				f(dig + str(i), i)
		f('', -1)
		return l


class Solution:

	def increasingNumbers(self, N):
		result = []
		self.addNumbers(0, result, 0, N)
		return result

	def addNumbers(self, currentNumber, result, digit, n):
		if digit == n:
			result.append(currentNumber)
			return
		currentDigit = currentNumber % 10
		if currentDigit == 9:
			return
		if n == 1:
			result.append(0)
		for num in range(currentDigit + 1, 10):
			newNumber = currentNumber * 10 + num
			self.addNumbers(newNumber, result, digit + 1, n)


class Solution:

	def increasingNumbers(self, N):
		number = []
		if N == 0:
			return number
		else:
			if N == 1:
				number.append(0)

			def digits(string, end):
				if len(string) == N:
					number.append(int(string))
				else:
					for i in range(end + 1, 11 - N + len(string)):
						digits(string + str(i), i)
			digits('', 0)
			return number


from itertools import combinations as combs
if __name__ == '__main__':
	for t in range(int(input())):
		N = int(input())
		if N == 1:
			print('0 1 2 3 4 5 6 7 8 9', end=' ')
		else:
			nums = '123456789'
			for comb in combs(nums, N):
				if list(comb) == sorted(comb):
					print(''.join(comb), end=' ')
		print()
quit()


def to_int(arr):
	ret = 0
	for i in arr:
		ret *= 10
		ret += i
	return ret

def helper(arr, l):
	if l == 0:
		yield to_int(arr)
		return
	if l < 0:
		return
	for i in range(arr[-1] + 1, 10):
		yield from helper(arr + [i], l - 1)

class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return list(range(10))
		ret = []
		for x in range(1, 10):
			for cand in helper([x], N - 1):
				ret.append(cand)
		return ret


class Solution:

	def validNumber(self, N: int, num: str) -> bool:
		return all([False if num[i] >= num[i + 1] else True for i in range(len(num) - 1)])

	def increasingNumbers(self, N):
		num = '123456789'
		res = [] if N > 1 else ['0']

		def solve(i: int, curr: str) -> list:
			if len(curr) == N:
				res.append(curr)
				return
			if i > 8 or len(curr) > N:
				return
			solve(i + 1, curr + num[i])
			solve(i + 1, curr)
		solve(0, '')
		return res


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return [str(i) for i in range(10)]
		prev = self.increasingNumbers(N - 1)
		ls = []
		for i in prev:
			if i != '0':
				for j in range(int(i[-1]) + 1, 10):
					ls.append(i + str(j))
		return ls


class Solution:

	def increasingNumbers(self, N):

		def solution(N, out, result, numbers, index):
			if len(out) == N:
				result.append(int(out))
				return
			for i in range(index, len(numbers)):
				solution(N, out + str(numbers[i]), result, numbers, i + 1)
		numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		if N == 1:
			return numbers
		result = []
		solution(N, '', result, numbers[1:], 0)
		return result


class Solution:

	def condition(self, s):
		prev = s[0]
		con = True
		for i in range(1, len(s)):
			if s[i] > prev:
				prev = s[i]
			else:
				con = False
				break
		if con:
			return s

	def increasingNumbers(self, n):
		st = 0
		ed = 10
		lst = []
		if n == 1:
			for i in range(10):
				lst.append(i)
			return lst
		elif n == 2:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					lst.append(int(str(i) + str(j)))
			return lst
		elif n == 3:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						lst.append(int(str(i) + str(j) + str(k)))
			return lst
		elif n == 4:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							lst.append(int(str(i) + str(j) + str(k) + str(l)))
			return lst
		elif n == 5:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							for m in range(l + 1, 10):
								lst.append(int(str(i) + str(j) + str(k) + str(l) + str(m)))
			return lst
		elif n == 6:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							for m in range(l + 1, 10):
								for n in range(m + 1, 10):
									lst.append(int(str(i) + str(j) + str(k) + str(l) + str(m) + str(n)))
			return lst
		elif n == 7:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							for m in range(l + 1, 10):
								for n in range(m + 1, 10):
									for o in range(n + 1, 10):
										lst.append(int(str(i) + str(j) + str(k) + str(l) + str(m) + str(n) + str(o)))
			return lst
		elif n == 8:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							for m in range(l + 1, 10):
								for n in range(m + 1, 10):
									for o in range(n + 1, 10):
										for p in range(o + 1, 10):
											lst.append(int(str(i) + str(j) + str(k) + str(l) + str(m) + str(n) + str(o) + str(p)))
			return lst
		elif n == 9:
			for i in range(1, 10):
				for j in range(i + 1, 10):
					for k in range(j + 1, 10):
						for l in range(k + 1, 10):
							for m in range(l + 1, 10):
								for n in range(m + 1, 10):
									for o in range(n + 1, 10):
										for p in range(o + 1, 10):
											for q in range(p + 1, 10):
												lst.append(int(str(i) + str(j) + str(k) + str(l) + str(m) + str(n) + str(o) + str(p) + str(q)))
			return lst


class Solution:

	def helper(self, num, N):
		if N == 0:
			self.output.append(num)
			return
		for i in range(1, 10):
			if num % 10 < i:
				self.helper(num * 10 + i, N - 1)

	def increasingNumbers(self, N):
		self.output = []
		if N == 1:
			self.output.append(0)
		self.helper(0, N)
		return self.output


class Solution:

	def increasingNumbers(self, N):

		def solve(start, N, num, List):
			if N == 0:
				List.append(num)
				return
			for i in range(start, 10):
				num = num * 10 + i
				solve(i + 1, N - 1, num, List)
				num = num // 10
		List = []
		if N == 1:
			for i in range(10):
				List.append(i)
			return List
		else:
			solve(1, N, 0, List)
		return List


class Solution:

	def increasingNumbers(self, N):
		lf = []
		if N == 1:
			for i in range(0, 10):
				lf.append(i)
			return lf
		self.helper(1, 0, N, lf)
		return lf

	def helper(self, start, curr, n, lf):
		if n == 0:
			lf.append(curr)
			return
		for i in range(start, 10):
			temp = curr * 10 + i
			self.helper(i + 1, temp, n - 1, lf)


class Solution:

	def increasingNumbers(self, N):
		if N <= 0 or N > 9:
			return []
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		before = self.increasingNumbers(N - 1)
		ans = list()
		for i in before:
			if i != 0:
				last = i % 10
				for a in range(last + 1, 10):
					ans.append(i * 10 + a)
		return ans


class Solution:

	def increasingNumbers(self, N):
		l = []
		k = self.seq('', '123456789', N, l)
		if N == 1:
			k.insert(0, 0)
		return k

	def seq(self, p, up, n, l):
		if len(p) == n:
			l.append(p)
			return
		if up == '':
			return
		else:
			ch = up[0]
			self.seq(p + ch, up[1:], n, l)
			self.seq(p, up[1:], n, l)
		return l


class Solution:

	def increasingNumbers(self, N):
		lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		templst = []
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		for i in range(N - 1):
			for l in lst:
				for j in range(1, 10):
					if l % 10 < j:
						templst.append(l * 10 + j)
			lst = templst.copy()
			templst = []
		return lst


class Solution:

	def increasingNumbers(self, N):
		graph = {}
		r = []
		m = []
		for i in range(1, N + 1):
			graph[i] = []
		graph[1] = [str(i) for i in range(10)]
		if N == 1:
			return graph[1]
		else:
			graph[1] = [str(i) for i in range(1, 10)]
			for i in range(2, N + 1):
				dp = graph[i - 1]
				for j in range(len(dp)):
					for k in range(0, 10):
						f = int(dp[j])
						f = f % 10
						if f < k:
							dp[j] = str(dp[j])
							m.append(dp[j] + str(k))
				graph[i] = m
				m = []
			t = graph[N]
			for i in range(len(t)):
				r.append(int(t[i]))
			return r


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		else:
			ans = list()
			self.c(ans, 0, '', N)
			return ans

	def c(self, ans, last, curr, n):
		if len(curr) == n:
			ans.append(int(curr))
		else:
			for digit in range(last + 1, 10):
				self.c(ans, digit, curr + str(digit), n)


class Solution:

	def increasingNumbers(self, n):
		ans = []
		if n == 1:
			return [i for i in range(10)]

		def fun(n, num):
			nonlocal ans
			if n == 0:
				ans.append(int(num))
				return
			for i in range(int(num[-1]) + 1, 10):
				fun(n - 1, num + str(i))
		fun(n, '0')
		return ans


class Solution:

	def increasingNumbers(self, N):
		arr = []

		def func(last, num, N):
			if N == 0:
				arr.append(num)
				return
			else:
				for i in range(last, 10):
					temp = num * 10 + i
					func(i + 1, temp, N - 1)
		if N == 1:
			for i in range(10):
				arr.append(i)
			return arr
		else:
			func(1, 0, N)
			return arr


class Solution:
	res = ''

	def increasingNumbers(self, N):
		if N == 1:
			return list(range(0, 10))
		Solution.res = ''
		self.printStrictlyInc(N)
		return [int(x) for x in self.res.split()]

	def printStrictlyInc(self, n, result='', prev='0'):
		if n == 0:
			Solution.res = Solution.res + result + ' '
			return
		for ch in range(ord(prev) + 1, ord('9') + 1):
			self.printStrictlyInc(n - 1, result + chr(ch), chr(ch))


class Solution:

	def increasingDigits(self, n, k, li, a):
		if n == 0:
			li.append(a)
			return
		for i in range(k, 10):
			num = 10 * a + i
			self.increasingDigits(n - 1, i + 1, li, num)
		return li

	def increasingNumbers(self, N):
		if N == 1:
			return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		else:
			li = []
			self.increasingDigits(N, 1, li, 0)
			return li


class Solution:

	def increasingNumbers(self, N):
		ans = []
		if N == 1:
			ans.append(0)

		def find_num(num, last):
			if len(num) == N:
				ans.append(num)
			else:
				for i in range(last + 1, 11 - N + len(num)):
					find_num(num + str(i), i)
		find_num('', 0)
		return ans


class Solution:

	def increasingNumbers(self, N):
		a = []
		s = ''
		if N == 1:
			a.append(0)

		def recursion(s):
			if len(s) == N:
				a.append(int(s))
			else:
				for i in range(1, 10):
					if s == '' or int(s[-1]) < i:
						recursion(s + str(i))
		recursion(s)
		return a


class Solution:

	def increasingNumbers(self, N):
		numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
		ans = []

		def addDigit(cn, cd, td):
			if cd == td:
				ans.append(cn)
			for i in numbers:
				if i > cn % 10:
					addDigit(cn * 10 + i, cd + 1, td)
		if N == 1:
			return numbers
		else:
			for i in numbers:
				if not i == 0:
					addDigit(i, 1, N)
		return ans


class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return list(range(10))

		def calc(a):
			s = 0
			for x in a:
				s = s * 10 + x
			return s
		ans = []

		def rec(a):
			if len(a) == N:
				ans.append(calc(a))
				return
			for i in range(1, 10):
				if a and a[-1] >= i:
					continue
				a.append(i)
				rec(a)
				a.pop()
		rec([])
		return ans


class Solution:

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

		def DFS(idx, lst, num):
			if len(lst) == N:
				ans.append(num[0])
				return
			for val in range(lst[-1] + 1, 10):
				DFS(idx + 1, lst + [val], [num[0] * 10 + val])
		for val in range(0, 10):
			if N > 1 and val == 0:
				pass
			else:
				DFS(1, [val], [val])
		return ans


class Solution:

	def increasingNumbers(self, N):
		l = list()

		def store(last, n, num, l):
			if n == 0:
				l.append(num)
			for i in range(last + 1, 10):
				a = num * 10 + i
				store(a % 10, n - 1, a, l)
		if N == 1:
			store(-1, 1, 0, l)
		else:
			store(0, N, 0, l)
		return l


class Solution:

	def increasingNumbers(self, N):
		self.ans = []
		self.recur('', 0, N)
		return self.ans

	def recur(self, n, l, sz):
		if l == sz:
			self.ans.append(int(n))
			return
		for i in range(10):
			if len(n) == 0:
				self.recur(str(i), l + 1, sz)
			elif int(n[-1]) < i and n[-1] != '0':
				self.recur(n + str(i), l + 1, sz)


def printStrictlyInc(n, result='', prev='0', l=[]):
	if n == 0:
		l.append(result)
		return
	for ch in range(ord(prev) + 1, ord('9') + 1):
		printStrictlyInc(n - 1, result + chr(ch), chr(ch), l)
	return l

class Solution:

	def increasingNumbers(self, N):
		if N == 1:
			return printStrictlyInc(N, '', '0', ['0'])
		else:
			return printStrictlyInc(N, '', '0', [])