解題說明
Restore IP Addresses
題目描述：給定一個只包含數字的字串 s，回傳所有可能的有效 IPv4 位址，這些位址可以通過在 s 中插入點號 . 來組成。有效的 IPv4 位址由四個整數（每個在 0 到 255 之間）以點號分隔，且每段不得有前導零（除了數字 0 本身）。
解題思路：使用回溯法逐段決定每個 IP 段的數字。從字串起點開始，嘗試取 1、2、3 個字元作為當前段，驗證是否合法（0–255 且無前導零）後遞迴處理剩餘字串，直到湊滿 4 段且字串恰好用完。
關鍵剪枝條件：
- 每段長度為 1 到 3，且數值不超過 255。
- 若開頭為
'0'，該段只能取長度 1。 - 已取 4 段但字串未用完，或字串已用完但不足 4 段，均提前剪枝。
- 剩餘字元數若超出剩餘段能容納的最大字元數（段數 × 3）或低於最小字元數（段數 × 1），也可剪枝。
C++ 解法
複雜度分析
時間複雜度：O(1)——由於 IP 位址固定由 4 段組成，每段最多 3 位數字，搜尋空間為常數（最多 3^4 = 81 種組合，加上剪枝後更少）。嚴格說是 O(M) 其中 M 為輸出結果數量（最多 O(3^4) = O(81)），字串長度 s 最長為 12，所以整體時間複雜度為 O(1)。
空間複雜度：O(1)——遞迴深度固定為 4，parts 向量最多 4 個元素，result 最多 O(81) 個字串。除輸出外所有輔助空間均為常數。
虛擬碼
1. Initialize result = [], parts = [].
2. Call backtrack(s, start=0, parts, result).
3. In backtrack(s, start, parts, result):
a. If len(parts) == 4:
- If start == len(s): add "parts[0].parts[1].parts[2].parts[3]" to result.
- Return.
b. Compute remaining_parts = 4 - len(parts), remaining_chars = len(s) - start.
c. If remaining_chars < remaining_parts or > remaining_parts * 3: return (prune).
d. For length in {1, 2, 3}:
- seg = s[start : start+length].
- If seg has leading zero and length > 1: break.
- If int(seg) > 255: break.
- Append seg to parts.
- Recurse: backtrack(s, start+length, parts, result).
- Pop seg from parts.
4. Return result.其他解法
方法一：純迭代三重迴圈 用三個迴圈變數 i、j、k 分別枚舉第一、二、三個分段點，計算四段字串並驗證合法性。時間複雜度同樣 O(1)（迴圈上界固定），程式碼更扁平直觀，無遞迴開銷，適合面試快速寫出。
方法二：動態規劃
定義 dp[i][k] 為「前 i 個字元恰好組成 k 個合法 IP 段」的所有後綴方案，逐層轉移。時間空間均 O(N × 4 × 3) = O(1)，但實作比回溯更繁瑣，且在此題規模下無實際優勢，僅作為練習 DP 思維的替代。
方法三：正規表達式（面試不推薦）
用 regex 模式 ^([01]?\d{1,2}|2[0-4]\d|25[0-5])\. 重複匹配四次。雖然程式碼短，但正規表達式在複雜模式下易出錯、效率不可控，面試中不建議使用。
延伸思考
- 若要還原 IPv6 位址（8 組，每組 1–4 位十六進位數字），回溯的結構需要如何修改？分段數量和合法性驗證有何不同？
- 在本題的剪枝策略中，若移除「剩餘字元數範圍」的剪枝，搜尋樹的節點數會增加多少？實際影響大嗎？
- 若輸入字串
s可能包含非數字字元，應在哪個階段進行合法性驗證最有效率？