Leetcode 967 Numbers With Same Consecutive Differences

题意

给定n，代表整数的长度，给定k代表两个相邻数字之间的间隔。求所有的值构成的组合

题目链接

https://leetcode.com/problems/numbers-with-same-consecutive-differences/description/

题解

dfs，有k位置要选，第一个位置我可以从1-9中选择，第二个位置是前一个位置的+k或者-k，要满足加减后的值满足>= 0并且 < k。注意k == 0的时候有重复，要去重。

class Solution {
public:vector<int> numsSameConsecDiff(int n, int k) {vector<int> res;for(int i = 1; i <= 9; i++) {dfs(i, 1, res, n, k);}return res;}void dfs(int x, int u, vector<int>& res, int n, int k) {if (u == n) {res.push_back(x);return;}int tmp = x % 10;if(tmp + k < 10) {dfs(x*10 + tmp + k, u+1, res, n, k);}if(tmp - k >= 0 && k != 0) {dfs(x*10 + tmp - k, u+1, res, n, k);}}
};

时间复杂度: $O(2^n)$
空间复杂度：$O(1)$