> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/numbers-with-same-consecutive-differences.md).

# Numbers With Same Consecutive Differences

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]
```

**Note:**

1. `1 <= N <= 9`
2. `0 <= K <= 9`

```java
class Solution {
    public int[] numsSameConsecDiff(int N, int K) {
        List<Integer> list = new ArrayList<>();
        if (N == 0)
            return new int[0];
        if (N == 1)
            list.add(0); // edge case
        dfs(N, K, list, 0);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            ans[i] = list.get(i);
        return ans;
    }

    public void dfs(int N, int K, List<Integer> list, int number) {
        // Base Case
        if (N == 0) {
            list.add(number);
            return;
        }
        for (int i = 0; i < 10; ++i) {
            // Do not add 0 at begining of a number
            if (i == 0 && number == 0)
                continue;
            // We add all the digits when we do not have any previous digit
            else if (number == 0 && i != 0)
                dfs(N - 1, K, list, i);
            else {
                // If the current digit, has a difference of K with last digit in number
                if (Math.abs((number % 10) - i) == K)
                    dfs(N - 1, K, list, number * 10 + i);
            }
        }
    }
}
```