一、題目深度解析與組合約束條件

題目描述

找出所有相加之和為n的k個數的組合，且滿足以下條件：

• 每個數只能使用一次（范圍為1到9）
• 所有數字均為唯一的正整數
• 組合中的數字按升序排列

例如，當k=3，n=9時，正確組合為[[1,2,6], [1,3,5], [2,3,4]]。題目要求返回所有可能的有效組合，且組合不能重復。

核心約束條件分析

與普通組合問題相比，本題增加了兩個關鍵約束：

1. 和約束：組合中所有元素的和必須等于n
2. 長度約束：組合的元素個數必須等于k

這兩個約束條件共同決定了回溯過程中的剪枝策略和終止條件，需要在回溯過程中動態維護當前組合的元素和與元素數量。

二、回溯解法的核心實現與邏輯框架

完整回溯代碼實現

class Solution {List<Integer> temp = new LinkedList<>();  // 存儲當前組合List<List<Integer>> res = new ArrayList<>();  // 存儲所有結果組合int sum = 0;  // 記錄當前組合的元素和public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 1, sum);  // 從1開始回溯return res;}public void backtracking(int k, int n, int start, int sum) {// 剪枝條件：和超過n或組合長度超過kif (sum > n || temp.size() > k) {return;}// 終止條件：和等于n且組合長度等于kif (sum == n && temp.size() == k) {res.add(new ArrayList<>(temp));  // 保存當前組合的副本return;}// 核心循環：動態計算循環上界，優化搜索空間for (int i = start; i <= 9 - (k - temp.size()) + 1; i++) {sum += i;  // 累加當前元素值temp.add(i);  // 選擇當前元素backtracking(k, n, i + 1, sum);  // 遞歸處理下一個元素sum -= i;  // 回溯：撤銷元素和累加temp.removeLast();  // 回溯：移除當前元素}return;}
}

核心設計解析：

1. 狀態變量維護：

   • temp：存儲當前正在構建的組合，使用LinkedList支持高效尾部操作
   • sum：記錄當前組合的元素和，用于快速判斷和約束
   • res：存儲所有符合條件的組合

2. 剪枝與終止條件：

   • sum > n：若當前和已超過目標值，直接剪枝
   • temp.size() > k：若組合長度已超過k，直接剪枝
   • sum == n && temp.size() == k：同時滿足和約束與長度約束時，保存結果

3. 循環邊界優化：

   • i <= 9 - (k - temp.size()) + 1：動態計算循環上界，確保剩余元素足夠選滿k個
   • 例如，當k=3且已選1個元素時，剩余需選2個元素，當前可選最大數為9 - 2 + 1 = 8

三、核心問題解析：多條件約束下的回溯邏輯

1. 雙重約束條件的處理

和約束的維護：

sum += i;  // 選擇元素時累加和
backtracking(..., sum);  // 遞歸傳遞當前和
sum -= i;  // 回溯時撤銷累加

通過在遞歸前后動態調整sum值，確保每次遞歸調用時都能正確傳遞當前組合的元素和。

長度約束的維護：

temp.size() > k  // 剪枝條件：長度超過k
temp.size() == k  // 終止條件：長度等于k

利用temp列表的長度作為判斷依據，結合和約束共同決定遞歸路徑的選擇與終止。

2. 循環邊界的數學推導

與普通組合問題類似，本題循環上界需滿足：

• 設當前已選t個元素，還需選m = k - t個元素
• 當前可選最大數i需滿足：i + m - 1 <= 9（因最大數為9）
• 推導得：i <= 9 - m + 1 = 9 - (k - t) + 1

示例說明：

當k=3，已選1個元素時：

• m = 3 - 1 = 2
• 循環上界：9 - 2 + 1 = 8
• 即當前可選范圍為1到8，確保后續能選夠2個元素

四、回溯流程深度模擬：以k=3,n=9為例

遞歸調用樹（部分展開）：

backtracking(3,9,1,0)
├─ i=1: sum=1, temp=[1]
│  └─ backtracking(3,9,2,1)
│    ├─ i=2: sum=3, temp=[1,2]
│    │  └─ backtracking(3,9,3,3)
│    │    ├─ i=3: sum=6, temp=[1,2,3] → 剪枝（和=6，繼續遞歸）
│    │    ├─ i=4: sum=7, temp=[1,2,4] → 剪枝
│    │    ├─ i=5: sum=8, temp=[1,2,5] → 剪枝
│    │    └─ i=6: sum=9, temp=[1,2,6] → 加入res
│    ├─ i=3: sum=4, temp=[1,3]
│    │  └─ backtracking(3,9,4,4)
│    │    └─ i=5: sum=9, temp=[1,3,5] → 加入res
│    └─ i=4: sum=5, temp=[1,4]
│       └─ backtracking(3,9,5,5)
│         └─ i=5: sum=10 → 剪枝（和>9）
├─ i=2: sum=2, temp=[2]
│  └─ backtracking(3,9,3,2)
│    ├─ i=3: sum=5, temp=[2,3]
│    │  └─ backtracking(3,9,4,5)
│    │    └─ i=4: sum=9, temp=[2,3,4] → 加入res
│    └─ i=4: sum=6, temp=[2,4] → 后續遞歸均剪枝
└─ i=3: sum=3, temp=[3] → 后續遞歸均剪枝

詳細步驟：

1. 初始調用：backtracking(3,9,1,0)

   • 從1開始選擇，初始和為0

2. 選擇1：

   • sum=1, temp=[1]
   • 遞歸選擇下一個數（從2開始）

3. 選擇2：

   • sum=3, temp=[1,2]
   • 遞歸選擇下一個數（從3開始）
   • 選擇6時，sum=9, temp=[1,2,6] → 滿足條件，加入結果集

4. 回退到選擇3：

   • sum=4, temp=[1,3]
   • 遞歸選擇5，sum=9, temp=[1,3,5] → 加入結果集

5. 回退到選擇2：

   • 選擇3，再選擇4，sum=9, temp=[2,3,4] → 加入結果集

6. 繼續回退與嘗試：

   • 其他路徑因和超過9或無法選滿3個數而被剪枝

五、算法復雜度分析

1. 時間復雜度

• O(C(9,k)×k)：
  • 組合數：C(9,k)為最終結果數量（從9個數中選k個的組合數）
  • 每個組合需要O(k)時間復制到結果集
• 優化后的循環邊界減少了無效搜索，但最壞情況下仍需遍歷所有可能組合

2. 空間復雜度

• O(k)：遞歸棧深度最大為k（每層遞歸代表一個數字選擇）
• temp列表長度最多為k，res空間為O(C(9,k)×k)

六、核心技術點總結：多約束回溯的關鍵要素

1. 多狀態變量維護

• 元素和：通過sum變量動態維護，確保快速判斷和約束
• 組合長度：通過temp.size()動態獲取，確保滿足長度約束
• 元素唯一性：通過start參數控制選擇范圍，確保元素不重復

2. 雙重剪枝策略

• 和剪枝：當sum > n時提前終止遞歸
• 長度剪枝：當temp.size() > k時提前終止遞歸

3. 循環邊界優化

• 數學推導動態上界，確保剩余元素足夠選滿k個
• 公式：i <= 9 - (k - temp.size()) + 1

七、常見誤區與優化建議

1. 狀態變量未回溯

• 誤區：忘記在遞歸后撤銷sum的累加

  sum += i;
  backtracking(...);
  // 缺少 sum -= i; 導致狀態未回退
  

• 正確做法：必須在遞歸調用后撤銷狀態變更，確保每次選擇的獨立性

2. 循環邊界錯誤

• 誤區：使用固定上界或錯誤的動態上界

  for (int i = start; i <= 9; i++) { ... } // 未優化上界，導致無效搜索
  

• 正確做法：使用i <= 9 - (k - temp.size()) + 1動態計算上界

3. 優化建議：位運算實現

// 位運算解法（僅作示意）
List<List<Integer>> res = new ArrayList<>();
for (int mask = 0; mask < (1 << 9); mask++) {if (Integer.bitCount(mask) == k) {List<Integer> combo = new ArrayList<>();int sum = 0;for (int i = 0; i < 9; i++) {if ((mask & (1 << i)) != 0) {combo.add(i + 1);sum += i + 1;}}if (sum == n) {res.add(combo);}}
}

• 優勢：代碼更簡潔，無需遞歸
• 劣勢：時間復雜度為O(2^9)，對大規模問題不適用

八、總結：多約束回溯的狀態管理之道

本算法通過回溯法在雙重約束條件下系統地枚舉所有可能組合，核心在于：

1. 狀態變量同步維護：同時跟蹤元素和、組合長度與元素選擇
2. 雙重剪枝優化：利用和約束與長度約束提前終止無效路徑
3. 動態邊界計算：通過數學推導減少搜索空間

理解多約束回溯問題的關鍵在于把握各狀態變量間的聯動關系，以及如何通過剪枝策略和循環邊界優化提升算法效率。這種方法不僅適用于組合總和問題，還可擴展到其他多約束條件下的組合優化問題。