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. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

&nbsp;
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]


&nbsp;
Constraints:


	2 &lt;= n &lt;= 9
	0 &lt;= k &lt;= 9


class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        # initialize the cache with all the valid numbers of length 1
        # cache is a list of tuple (number, digit at units place)
        cache = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]
        cacheTemp = []
        
        # each iteration will store all the valid numbers of length 2 to n in cache
        for i in range(2, n + 1):
            # loop through the cache from the previous iteration
            for j in cache:
                if k == 0:
                    if j[0] != 0:
                        cacheTemp.append((j[0] * 10 + j[1], j[1]))
                elif j[1] == 0 and i == 2:
                    continue
                elif j[1] <= k - 1:
                    if j[1] < 10 - k:
                        cacheTemp.append((j[0] * 10 + j[1] + k, j[1] + k))
                elif j[1] >= 10 - k:
                    if j[1] > k - 1:
                        cacheTemp.append((j[0] * 10 + j[1] - k, j[1] - k))
                else:
                    cacheTemp.append((j[0] * 10 + j[1] - k, j[1] - k))
                    cacheTemp.append((j[0] * 10 + j[1] + k, j[1] + k))
            cache = cacheTemp   # store the list of valid integers of length i in cache
            cacheTemp = []  # empty the temporary list
        
        res = []
        for i in cache:
            res.append(i[0])
        
        return res
        
class Solution {
    
    List<Integer> res = new ArrayList<>();
    public int[] numsSameConsecDiff(int n, int k) {
        
        for(int ans = 1; ans < 10; ans++){ // first digit can't be 0
            find(ans, n-1, k); // find remaining n-1 digits using backtrack
        }
        
        return res.stream().mapToInt(Integer::intValue).toArray();  // convert list to int arr
    }
    
    private void find(int ans, int n, int k){
        
        if(n == 0){
            res.add(ans); // if got length n number then put that into res
            return;
        }
        
        for(int i = 0; i < 10; i++){
            if(Math.abs(ans%10-i) == k) // find digit that have k difference with last digit
                find(ans*10+i, n-1, k);
        }
        ans /= 10; // remove last digit while backtrack
    }
}
class Solution {
public:
    vector<int> res;
    void solve(int num,int n,int k)
    {
        if(n==1)
        {
            res.push_back(num);
            return;
        }
        int dig=num%10;
        if(dig+k<=9 && k!=0)
        {
            solve(num*10+dig+k,n-1,k);
        }
        if(dig-k>=0)
        {
            solve(num*10+dig-k,n-1,k);
        }
    }
    vector<int> numsSameConsecDiff(int n, int k) {
        res.clear();
        for(int i=1;i<=9;++i)
        {
            solve(i,n,k);
        }
        return res;
    }
};
/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {

  let res = [];

  const bfs=(num,i)=>{
    let queue = [];
    queue.push(i);
    while(queue.length){
        // console.log("queue is ",queue)
        i = queue.shift();
        if (i <= num)
        {
            if(i.toString().length===n){
               res.push(i);
            }
            let last_digit = i % 10;

            if (last_digit+k<10)
            {
                queue.push((i * 10) + (last_digit + k));
            }
            if(k>0 && last_digit-k >= 0)
             {
                queue.push((i * 10) + (last_digit-k));
             }

        }
    }
  }

  let num = Math.pow(10,n)-1;
  for(let i=1;i<=9 && i<num ;i++){
    bfs(num,i);
  }
  return res;

};
Numbers With Same Consecutive Differences