## [Leetcode]967. Numbers With Same Consecutive Differences (C++)

### 题目描述

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.

### 例子

#### 例子 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.

#### 例子 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`

### 解题思路

• 0.如果当前数组已经符合要求，则添加进结果并返回 -> 这道题是看数字长度是否满足 `N`
• 1.往当前数组添加下一个可能的元素 -> 这道题是往数字后面添加当前最后一位数字 +/- K 的数字
• 2.在新添加的元素后面递归调用自身 -> 这道题是针对新产生的数字进行递归调用自身
• 3.上一步处理完成后，要把添加的元素推出去，恢复原来的状态 -> 这道题是将新增加的数字去掉
• 4.重复 1 步骤

``````#include <vector>
#include <string>

class Solution {
public:
std::vector<int> numsSameConsecDiff(int N, int K) {
if (N == 1) {
return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
}
std::string curr_num;
std::vector<int> candidates;
for (int i = 1; i < 10; i++) {
curr_num = std::to_string(i);
findNumbers(N, K, curr_num, candidates);
}
return candidates;
}

private:
void findNumbers(int N, int K, std::string& curr_num, std::vector<int>& candidates) {
if (curr_num.length() == N) {
candidates.push_back(std::stoi(curr_num));
return;
}

char last_digit = curr_num.back();
char next_digit = last_digit - K;
if (std::isdigit(next_digit)) {
curr_num.push_back(next_digit);
findNumbers(N, K, curr_num, candidates);
curr_num.pop_back();
}

if (K != 0) {
next_digit = last_digit + K;
if (std::isdigit(next_digit)) {
curr_num.push_back(next_digit);
findNumbers(N, K, curr_num, candidates);
curr_num.pop_back();
}
}
}
};
``````
• 时间复杂度：O(2^n)
• 空间复杂度：O(n) <- 不算输出结果的空间，只算堆栈产生的空间