Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.
Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.
You may return the answer in any order.
 
Example 1:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 3:
Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]

Example 4:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 5:
Input: n = 2, k = 2
Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

 
Constraints:

2 <= n <= 9
0 <= k <= 9

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Graph traversal

Complete search

Starter code: class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        

Solutions:
class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		if n == 1:
			return [i for i in range(10)]
		queue = [digit for digit in range(1, 10)]
		for level in range(n - 1):
			next_queue = []
			for num in queue:
				tail_digit = num % 10
				next_digits = set([tail_digit + k, tail_digit - k])
				for next_digit in next_digits:
					if 0 <= next_digit < 10:
						new_num = num * 10 + next_digit
						next_queue.append(new_num)
			queue = next_queue
		return queue


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		if n == 1:
			return list(range(10))
		ans = []
		for num in range(1, 10):
			self.dfs(n - 1, num, ans, k)
		return ans

	def dfs(self, n, num, ans, k):
		if n == 0:
			return ans.append(num)
		last_digit = num % 10
		next_ds = set([last_digit + k, last_digit - k])
		for digit in next_ds:
			if 0 <= digit < 10:
				tmp = num * 10 + digit
				self.dfs(n - 1, tmp, ans, k)


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		queue = []
		ans = []
		for i in range(1, 10):
			queue.append(str(i))
		while len(queue) > 0:
			num = queue.pop(0)
			if len(num) == n and num not in ans:
				ans.append(num)
			elif len(num) < n:
				x = int(num[-1])
				if x - k >= 0:
					queue.append(num + str(x - k))
				if x + k <= 9:
					queue.append(num + str(x + k))
		return ans


class Solution:

	def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
		ans = []

		def DFS(N, num):
			if N == 0:
				return ans.append(num)
			tail_digit = num % 10
			next_digits = set([tail_digit + K, tail_digit - K])
			for next_digit in next_digits:
				if 0 <= next_digit < 10:
					new_num = num * 10 + next_digit
					DFS(N - 1, new_num)
		for num in range(1, 10):
			DFS(N - 1, num)
		return list(ans)


class Solution:

	def numsSameConsecDiff(self, n, k):
		res = []
		for i in range(1, 10):
			neighbors = self.helper(i, k)
			for neighbor in neighbors:
				res.append([i, neighbor])
		if n > 2:
			n -= 2
			while n > 0:
				temp = []
				for sublist in res:
					neighbors = self.helper(sublist[-1], k)
					for neighbor in neighbors:
						temp.append(sublist + [neighbor])
				n -= 1
				res = temp
		for i in range(len(res)):
			res[i] = int(''.join((str(ele) for ele in res[i])))
		return res

	def helper(self, val, k):
		res = set()
		if val + k <= 9:
			res.add(val + k)
		if val - k >= 0:
			res.add(val - k)
		return res


class Solution:

	def numsSameConsecDiff(self, N: int, K: int) -> List[int]:

		def dfs(N, K, digit, rst):
			if not N:
				rst.append(int(''.join(map(str, digit))))
				return
			if digit[-1] + K <= 9:
				dfs(N - 1, K, digit + [digit[-1] + K], rst)
			if digit[-1] - K >= 0:
				dfs(N - 1, K, digit + [digit[-1] - K], rst)
		if N == 1:
			return list(range(10))
		if K == 0:
			return [int(str(i) * N) for i in range(1, 10)]
		rst = []
		for i in range(1, 10):
			dfs(N - 1, K, [i], rst)
		return rst


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:

		def solve(x):
			s = str(x)
			if len(s) > 1 and abs(int(s[-1]) - int(s[-2])) != k:
				return
			if len(s) == n and abs(int(s[-1]) - int(s[-2])) == k:
				result.append(x)
			if len(s) == n:
				return
			for i in range(0, 10):
				solve(x * 10 + i)
		result = []
		for i in range(1, 10):
			solve(i)
		return result


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		result = {1, 2, 3, 4, 5, 6, 7, 8, 9}
		for i in range(1, n):
			temp = list()
			for r in result:
				if k == 0:
					temp.append(r * 10 + r % 10)
				else:
					back = r % 10
					if back - k >= 0:
						temp.append(r * 10 + back - k)
					if back + k < 10:
						temp.append(r * 10 + back + k)
			result = temp.copy()
		return result


class Solution:

	def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
		dp = list(range(10))
		for _ in range(N - 1):
			_dp = set()
			for x in dp:
				for y in [x % 10 + K, x % 10 - K]:
					if x and 0 <= y <= 9:
						_dp.add(x * 10 + y)
			dp = _dp
		return list(dp)


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		import math
		from collections import deque
		deq = deque([i for i in range(1, 10)])
		res = []
		while deq:
			num = deq.popleft()
			if math.pow(10, n - 1) <= num < math.pow(10, n):
				res.append(num)
			else:
				targets = [num % 10 - k, num % 10 + k] if k > 0 else [num % 10]
				for target in targets:
					if 0 <= target <= 9:
						deq.append(num * 10 + target)
		return res


import itertools

class Solution:

	def step(self, n, k):
		d = n % 10
		b = n * 10
		if k == 0:
			yield (b + d)
		if d < d + k < 10:
			yield (b + d + k)
		if 0 <= d - k < d:
			yield (b + d - k)

	def solve(self, nums, n, k):
		if n == 1:
			return nums
		soln = [self.step(x, k) for x in nums]
		return itertools.chain.from_iterable([self.solve(x, n - 1, k) for x in soln])

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
		seed = [x for x in range(1, 10) if x + k < 10 or 0 <= x - k < 10]
		return list(self.solve(seed, n, k))


class Solution:

	def numsSameConsecDiff(self, n: int, k: int) -> List[int]:

		@functools.lru_cache(maxsize=128, typed=False)
		def check(n, k, s):
			rtv = []
			if n == 0:
				return []
			rtv = []
			for i in range(10):
				if abs(i - s) == k:
					r1 = check(n - 1, k, i)
					if r1:
						for r in r1:
							rtv.append([i] + r)
					else:
						rtv.append([i])
			return rtv
		rtv = []
		for i in range(1, 10):
			r0 = check(n - 1, k, i)
			for r in r0:
				t = i
				for c in r:
					t = t * 10 + c
				rtv.append(t)
		return rtv