解題說明
Combination Sum III
題目描述：找出所有由 1–9 中恰好 k 個不重複數字組成、且總和等於 n 的組合。
解題思路：用回溯法（Backtracking）逐步選取數字。從當前起始值 start 往後枚舉，加入候選數字後遞迴，直到選滿 k 個且總和為 n 時記錄結果。因數字只用 1–9 且不可重複，無需額外去重邏輯；當剩餘和或剩餘個數不足時提前剪枝，大幅減少搜索空間。
C++ 解法
複雜度分析
時間複雜度：O(C(9,k) × k) — 最多從 9 個數字中選 k 個，每個組合記錄需 O(k)。
空間複雜度：O(k) — 遞迴深度最多 k 層，current 陣列最多 k 個元素。
虛擬碼
1. Define backtrack(start, k, remaining, current):
a. If len(current) == k and remaining == 0: record current
b. If len(current) == k or remaining <= 0: return
c. For i from start to 9:
- Pruning: if not enough numbers left, break
- Add i to current
- Recurse: backtrack(i+1, k, remaining-i, current)
- Remove i from current
2. Call backtrack(1, k, n, [])
3. Return result其他解法
位元遮罩枚舉 O(2^9)：枚舉 1–9 的所有子集，檢查大小是否為 k 且總和為 n。寫法直觀但效率略低，適合數字範圍小時快速實作。
動態規劃：dp[i][j][s] 表示用前 i 個數選 j 個湊出總和 s 的方案數，但難以還原具體組合，通常不如回溯法直觀。
延伸思考
- 若數字可重複使用（Combination Sum II 風格），回溯邏輯需如何調整？
- 如何改寫成迭代（BFS 層序展開）的版本？
- 若要求輸出方案總數而非具體組合，能否用 DP 在 O(k × n) 時間內解決？