目錄
問題描述
解決思路
關鍵點
代碼實現
代碼解析
1. 初始化結果和路徑
2. 深度優先搜索（DFS）
3. 遍歷候選數字
4. 遞歸與回溯
示例分析
復雜度與優化
回溯算法三部曲
1. 路徑選擇：記錄當前路徑
2. 遞歸探索：進入下一層決策
3. 撤銷選擇：回溯到上一層
?代碼框架模板
關鍵點解析
總結
問題描述
我們需要找出所有由?k?個不同數字組成的組合，這些數字的范圍是?1 到 9，且它們的和等于?n。組合中的數字不能重復使用，且結果不能包含重復的組合。例如，當?k=3, n=7?時，唯一有效的組合是?[1,2,4]。
解決思路
這個問題可以通過回溯算法解決。核心思想是遞歸地嘗試每一個可能的數字，逐步構建符合條件的組合，并通過剪枝優化減少無效搜索。
關鍵點
-
數字范圍固定：所有數字只能在?
1-9?中選擇。 -
組合唯一性：每個組合中的數字必須嚴格遞增，避免重復（如?
[1,2,4]?和?[2,1,4]?被視為同一組合）。 -
剪枝優化：在遞歸過程中，提前終止不可能滿足條件的分支，大幅提高效率。
代碼實現
var combinationSum3 = function (k, n) {const result = [];const path = [];const dfs = (start, sum) => {// 終止條件：路徑長度等于k且和等于nif (path.length === k && sum === n) {result.push([...path]);return;}// 遍歷候選數字for (let i = start; i <= 9; i++) {// 剪枝1：剩余數字不夠組成k個數if (path.length + (9 - i + 1) < k) break; // 剪枝2：當前和超過nif (sum + i > n) break; path.push(i);dfs(i + 1, sum + i); // 遞歸下一層，起始位置為i+1path.pop(); // 回溯，撤銷選擇}};dfs(1, 0); // 從數字1開始，初始和為0return result;
};代碼解析
1. 初始化結果和路徑
-
result：存儲所有符合條件的組合。 -
path：記錄當前遞歸路徑中的數字。
2. 深度優先搜索（DFS）
-
參數：
start?表示當前遞歸的起始數字，sum?表示路徑中數字的當前和。 -
終止條件：當路徑長度等于?
k?且和等于?n?時，將當前路徑加入結果列表。
3. 遍歷候選數字
-
循環范圍：從?
start?到?9，確保數字遞增，避免重復組合。 -
剪枝1：
path.length + (9 - i + 1) < k
如果當前已選數字數量加上剩余可用數字數量不足?k，說明無法組成有效組合，直接終止循環。
例如：k=3，當前已選1個數字，剩余可用數字是?8?和?9（共2個），顯然不夠選2個。 -
剪枝2：
sum + i > n
如果當前路徑和加上?i?已經超過?n，后續更大的數字只會讓和更大，無需繼續搜索。
4. 遞歸與回溯
-
選擇數字：將?
i?加入路徑，遞歸調用?dfs?處理下一個數字。 -
撤銷選擇：遞歸返回后，將?
i?從路徑中移除，嘗試其他可能的數字。
示例分析
以?k=3, n=7?為例：
-
初始調用：
dfs(1, 0)。 -
第一層循環：
i=1，路徑為?[1]，和為1。 -
第二層循環：
i=2（起始為2），路徑為?[1,2]，和為3。 -
第三層循環：
i=4（起始為3），路徑為?[1,2,4]，和為7，滿足條件，加入結果。 -
回溯：遞歸返回，嘗試其他數字，但均無法滿足條件，最終結果唯一。
復雜度與優化
-
時間復雜度：最壞情況為?
O(9! / (k!(9-k)!))，即組合數的時間。 -
空間復雜度：遞歸棧深度為?
k，空間復雜度為?O(k)。
通過剪枝，實際運行時間遠低于理論最壞情況，因為無效分支被提前終止。
回溯算法三部曲
回溯算法是解決組合、排列、子集等問題的經典方法。它的核心思想是遞歸地嘗試所有可能的選擇，并通過“撤銷選擇”回到之前的狀態，從而窮舉所有解。其實現過程可以總結為以下三個關鍵步驟：
1. 路徑選擇：記錄當前路徑
在每一步遞歸中，將當前的選擇加入路徑（通常是一個數組），表示“當前正在嘗試這個選擇”。
對應代碼：path.push(i)
作用：保存當前遞歸層的選擇，用于后續判斷是否滿足條件。
示例：在組合問題中，選擇數字?i?加入?path，表示嘗試將?i?作為組合的一部分。
2. 遞歸探索：進入下一層決策
基于當前路徑，遞歸調用函數，處理下一個選擇（比如下一個數字或位置）。
對應代碼：dfs(i + 1, sum + i)
作用：進入下一層遞歸，繼續嘗試剩余的選擇。
示例：在組合問題中，遞歸時從?i+1?開始，確保數字不重復且遞增，避免重復組合。
3. 撤銷選擇：回溯到上一層
當遞歸返回后（即完成當前分支的探索），將最后加入路徑的元素移除，回到上一層狀態，嘗試其他可能的選擇。
對應代碼：path.pop()
作用：撤銷當前層的選擇，保證路徑的正確性，避免污染其他分支。
示例：組合問題中，當嘗試完以?i?開頭的所有組合后，移除?i，嘗試下一個數字。
?代碼框架模板
function backtrack(路徑, 選擇列表) {if (滿足終止條件) {將路徑加入結果;return;}for (選擇 in 選擇列表) {做選擇：將選擇加入路徑;backtrack(路徑, 新的選擇列表); // 進入下一層遞歸撤銷選擇：將選擇從路徑移除; // 回溯}
}關鍵點解析
-
路徑的維護
path?數組記錄當前遞歸路徑的選擇，必須通過?push?和?pop?確保狀態正確。 -
遞歸與回溯的關系
遞歸是縱向深入探索一條路徑，回溯是橫向嘗試其他可能的選擇。遞歸的終點是終止條件，回溯的觸發點是遞歸返回后的?pop。 -
剪枝優化
在組合問題中，通過以下兩種剪枝大幅減少遞歸次數：-
剩余數字不足：
path.length + (9 - i + 1) < k
例如：如果還需要選 2 個數字，但剩余可用數字只有 1 個，直接終止。 -
和超過目標值：
sum + i > n
當前路徑和已經超過?n，無需繼續遞歸
-
?
總結
該問題通過回溯算法枚舉所有可能的組合，結合剪枝策略（剩余數字不足、和超過目標值）顯著提高效率。核心在于：
-
遞增選擇數字：避免重復組合。
-
剪枝優化：減少不必要的遞歸調用。
-
回溯機制：撤銷選擇以嘗試其他可能。
這種模式適用于許多組合問題，如子集、排列、組合總和等。
