https://leetcode.com/problems/numbers-with-same-consecutive-differences

Let us try to build our number digit by digit. Define dfs(i,j), where i is number of digits we build so far and j is the last digit in builded numbers. For example dfs(3,2) = [212, 432, 232]. We need to:

  1. if j not in [0,9] we return [], there is not numbers and also if j==0 and i = 1, it means, that first digit is zero. However there is one exeption, if N == 1, we need to return all 10 digits.
  2. if i == 1, than there is only one desired number, j.
  3. Also we need to be careful with case K = 0, it this case we have only one option how to build next digit: dfs(i-1,j), and if K != 0, we have two options: dfs(i-1, j+K) and dfs(i-1,j-K).
  4. Finally, we need to run dfs(N,i) for every digit.

Complexity: time complexity is O(2^(n-1) * 10), because we start with all digits and then each step we have at most two options. Space complexity is the same and it can be reduced if we use integers instead of strings.

class Solution:
    def numsSameConsecDiff(self, N, K):
        @lru_cache(None)
        def dfs(i,j):
            if j < 0 or j > 9 or (j == 0 and i == 1): return []
            if i == 1: return [str(j)]
            dirs, out = set([K, -K]), []
            for d in dirs:
                out += [s+str(j) for s in dfs(i-1,j+d)]
            return out
        
        if N == 1: return range(10)
        return list(chain(*[dfs(N, i) for i in range(10)]))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0967