** * @param {number} k * @param {number} n * @return {number[][]} */ const combinationSum3 = (k, n) => { // 1. 記錄結果集 const result = []; // 2. 遞歸：index -> 索引，sum -> 當前和，path -> 路徑 const recursion = (index, sum, path) => { // 2.1 設置遞歸終止條件：如果它的路徑長度等于 k if (path.length === k) { // 2.1.1 設置收割條件，當它的和為 n 的時候 if (sum === n) { result.push(path.concat()); } // 2.1.2 終止后續遞歸 return; } // 2.2 遍歷 [index, 9]，從中挑選數字進入 path for (let i = index; i <= 9; i++) { // 2.2.1 如果 sum + i > n，表明和超標了，沒必要下一輪遞歸 if (sum + i > n) { break; } // 2.2.2 回溯常用，進進出出的套路 path.push(i); recursion(i + 1, sum + i, path); path.pop(); } }; recursion(1, 0, []); // 3. 返回結果 return result; }; console.log(combinationSum3(3, 7)); // [ [ 1, 2, 4 ] ] console.log(combinationSum3(3, 9)); // [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]