題目： LeetCode - 967. Numbers With Same Consecutive Differences

題目說明

給兩個整數，N 代表位數，K 代表兩個數字的差，求為 N 位數且鄰近兩個數值的差為 K 的所有數。

解題思路

當我們要在一個數後面添加一位數字時，那個數字一定是原本數的最後一位數加 K 或減 K，依照此想法使用遞迴填完數字即可。需要注意的是當 N 為 1 時答案為 {0, 1, 2, ..., 9}，所以需要放入 0。而當 K 為 0 時，l + k 會等於 l - k，所以要排除避免出現兩個相同的數字。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        vector<int> v;
        if(N == 1) v.emplace_back(0);
        for(int i = 1; i <= 9; ++i) dfs(N - 1, K, i, v);
        return v;
    }
private:
    void dfs(int N, int K, int cur, vector<int>& v)
    {
        if(!N) { v.emplace_back(cur); return; }
        int l = cur % 10;
        if(l + K <= 9) dfs(N - 1, K, cur * 10 + l + K, v);
        if(l - K >= 0 && K) dfs(N - 1, K, cur * 10 + l - K, v);
    }
};