Số bước nhảy (Stepping Numbers) trong C++

Cho low và high, tìm tất cả số "bước nhảy" (Stepping Numbers) trong khoảng [low, high]. Số bước nhảy là số mà hiệu tuyệt đối giữa hai chữ số liền kề luôn bằng 1.

Ví dụ: low = 0, high = 21 → [0,1,2,3,4,5,6,7,8,9,10,12,21].

Thuật toán giải quyết (DFS sinh số)

1. Hàm solve(high, seed, len):
   • Nếu seed > high → dừng.
   • Thêm seed vào mảng tạm.
   • Nếu seed == 0: sinh các số 1 chữ số 1..9.
   • Ngược lại: lấy chữ số cuối last = seed % 10.
     • Nếu last >= 1 và len+1 <= 10 → solve(high, seed*10 + last-1, len+1).
     • Nếu last <= 8 và len+1 <= 10 → solve(high, seed*10 + last+1, len+1).
2. Gọi solve(high, 0, 0).
3. Sắp xếp mảng tạm, lọc các số >= low.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

typedef long long lli;

class Solution {
    vector<lli> temp;
    void solve(int high, lli seed = 0, int len = 0) {
        if (seed > high) return;
        temp.push_back(seed);
        if (!seed) {
            for (int i = 1; i <= 9; i++) solve(high, i, 1);
        } else {
            int last = seed % 10;
            if (last >= 1 && len + 1 <= 10) solve(high, seed * 10 + last - 1, len + 1);
            if (last <= 8 && len + 1 <= 10) solve(high, seed * 10 + last + 1, len + 1);
        }
    }
public:
    vector<int> countSteppingNumbers(int low, int high) {
        solve(high);
        sort(temp.begin(), temp.end());
        vector<int> ans;
        for (lli x : temp) if (x >= low) ans.push_back(x);
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.countSteppingNumbers(0, 40));
}

Đầu vào

0 40

Đầu ra

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, ]