解題說明
Iterator for Combination
題目描述： 設計一個 CombinationIterator 類別，接收一個由互不相同的小寫英文字母組成的排序字串 characters 和一個整數 combinationLength。實現 next() 回傳下一個長度為 combinationLength 的組合（按字典序），以及 hasNext() 判斷是否還有下一個組合。
解題思路： 使用索引陣列來追蹤當前組合中每個字元的位置。初始化時，索引設為 [0, 1, 2, ..., combinationLength-1]。每次呼叫 next() 時，先根據當前索引建構結果字串，然後將索引推進到下一個有效的組合。推進邏輯：從最右邊的索引開始，找到可以遞增的位置（即不會超出範圍），遞增後將其右邊的索引依次設置為連續值。
C++ 解法
複雜度分析
時間複雜度：next() 為 O(k)，hasNext() 為 O(1)。其中 k 為 combinationLength
空間複雜度：O(k) — 儲存索引陣列
虛擬碼
1. Initialize: store characters string, set indices = [0, 1, ..., k-1], hasMore = true 2. next(): a. Build result string from chars[indices[0..k-1]] b. Find rightmost index i where indices[i] < n - k + i c. If no such i exists, set hasMore = false d. Otherwise, increment indices[i] and set indices[j] = indices[j-1] + 1 for j > i e. Return result 3. hasNext(): return hasMore
其他解法
方法二：預計算所有組合 在建構子中用回溯法預先產生所有組合並存入佇列。next() 直接從佇列取出。優點是 next() 為 O(1)，缺點是初始化需要 O(C(n,k) × k) 的時間和空間，當 n 較大時可能浪費記憶體。
方法三：位元遮罩（Bitmask） 用一個整數的二進位表示來追蹤選擇了哪些字元。從 (1<<n)-1 開始往下遞減，找到恰好有 k 個 1 的數字即為有效組合。優點是概念簡潔，缺點是可能需要跳過許多無效的數字。
延伸思考
- 如果字元可以重複（允許重複組合），你會如何修改迭代器？
- 能否實現一個 prev() 方法，回到上一個組合？這對空間複雜度有什麼影響？
- 如果組合長度不固定，需要同時迭代所有可能長度的組合（按字典序），你會如何設計？