967. Numbers With Same Consecutive Differences

问题：

求位数为n，相邻数字之间绝对值为k的所有数的可能性。

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]

Example 3:
Input: n = 2, k = 0
Output: [11,22,33,44,55,66,77,88,99]

Example 4:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 5:
Input: n = 2, k = 2
Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]
 
Constraints:
2 <= n <= 9
0 <= k <= 9

解法：Backtracking（回溯算法）

状态：到当前位为止，构成的前几位数字。path
选择：
- 第1位：1～9
- 第1位以外：当前结果的最后一位path.back()，为基准+k or -k 后得到的数字满足：0～9
  - ⚠️ 注意：特别的，若k=0，则只求一遍。
递归退出条件：path.length==n

代码参考：

 1 class Solution {
 2 public:
 3     bool isValid(char obj) {
 4         return (obj>='0' && obj<='9');
 5     }
 6     void backtrack(vector<int>& res, int n, int k, string path) {
 7         if(path.length() == n) {
 8             res.push_back(atoi(path.c_str()));
 9             return;
10         }
11         char cur;
12         if(path.length()==0) {
13             for(int i=1; i<=9; i++) {
14                 cur = '0'+i;
15                 backtrack(res, n, k, path+cur);
16             }
17         } else {
18             if(isValid(path.back()+k)) {
19                 cur=path.back()+k;
20                 backtrack(res, n, k, path+cur);
21             } 
22             if(k!=0 && isValid(path.back()-k)){
23                 cur=path.back()-k;
24                 backtrack(res, n, k, path+cur);
25             }
26         }
27         return;
28     }
29     vector<int> numsSameConsecDiff(int n, int k) {
30         vector<int> res;
31         backtrack(res, n, k, "");
32         return res;
33     }
34 };