题目描述

返回所有长度为 N 且满足其每两个连续位上的数字之间的差的绝对值为 K 的非负整数。

请注意，除了数字 0 本身之外，答案中的每个数字都不能有前导零。例如，01 因为有一个前导零，所以是无效的；但 0 是有效的。

你可以按任何顺序返回答案。

样例

输入：N = 3, K = 7
输出：[181,292,707,818,929]
解释：注意，070 不是一个有效的数字，因为它有前导零。

输入：N = 2, K = 1
输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

注意

• 1 <= N <= 9
• 0 <= K <= 9

算法

(递归) $O(2^N)$

• 采用递归的方式，从高位开始逐一填数字，除最高位外，每一位最多有两种填法，分别尝试即可。

时间复杂度

• 最坏情况下，除最高位外，每一位都有两种填法，故时间复杂度为 $O(2^N)$。

C++ 代码

class Solution {
public:

    void solve(int depth, int num, int N, int K, vector<int> &ans) {
        if (depth == 0) {
            ans.push_back(num);
            return;
        }

        if (depth == N) {
            for (int i = 1; i <= 9; i++)
                solve(depth - 1, i, N, K, ans);
            if (N == 1)
                solve(depth - 1, 0, N, K, ans);
        }

        else {
            int last = num % 10;

            if (last + K <= 9)
                solve(depth - 1, num * 10 + last + K, N, K, ans);

            if (K != 0 && last - K >= 0)
                solve(depth - 1, num * 10 + last - K, N, K, ans);
        }

    }

    vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> ans;
        solve(N, 0, N, K, ans);

        return ans;
    }
};