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