LeetCode 解題筆記：1291. Sequential Digits

作者：王一哲
日期：2026年7月13日


LeetCode 題目連結：1291. Sequential Digits

解題想法

中等難度的題目。這題考 dfs，自訂 dfs 的函式，輸入目前的數字 $curr$，最後一位數字 $last$，如果 $curr > high$ 不可能再有解，return；如果 $low \leq curr \leq high$，在範圍內，新增 $curr$ 至 $ans$；如果 $last < 9$ 還有新的數字，遞迴。最後要將 $ans$ 排序再輸出。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 30.59%.

cclass Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        
        def dfs(curr, last):
            # 代入目前的數字 curr，最後一位數字 last
            # 超出上限，不可能有新的答案
            if curr > high: return
            # 在範圍內，新增答案
            if low <= curr <= high:
                ans.append(curr)
            # 更新 curr
            if last < 9:
                nxt = last + 1
                dfs(curr * 10 + nxt, nxt)
        # End of DFS. 以 1 ~ 9 為起點各跑一次 dfs
        for i in range(1, 10):
            dfs(i, i)
        # 答案要排序後再輸出
        ans.sort()
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.68 MB, beats 5.54%.

class Solution {
public:
    vector<int> ans;
    void dfs(int curr, int last, const int low, const int high) {
        // 代入目前的數字 curr，最後一位數字 last
        // 超出上限，不可能有新的答案
        if (curr > high) return;
        // 在範圍內，新增答案
        if (curr >= low && curr <= high) {
            ans.push_back(curr);
        }
        // 更新 curr
        if (last < 9) {
            int nxt = last + 1;
            dfs(curr * 10 + nxt, nxt, low, high);
        }
    }

    vector<int> sequentialDigits(int low, int high) {
        // 以 1 ~ 9 為起點各跑一次 dfs
        for(int i = 1; i <= 9; i++) {
            dfs(i, i, low, high);
        }
        // 答案要排序後再輸出
        sort(ans.begin(), ans.end());
        return ans;
    }
};