回溯part02
216. 組合總和 III
/*** @param {number} k* @param {number} n* @return {number[][]}*/
var combinationSum3 = function(k, n) {// k個數字相加為n// 只能使用1-9// 每個數字只能使用一次// 不能重復 如 1 2 4 、 4 1 2 不可以let res = [];backtracking(k, n, [], 0, 1, res);return res;
};function backtracking(k, n, path, curSum, startIndex, res){//找到滿足條件的組合if(curSum == n && path.length == k){res.push([...path]);return;}//遞歸邊界//現在取的值相加已經大于目標值了//當前取的個數大于k個了，迭代的深度if(curSum > n || path.length > k) return;//1-9只能用一次，不能重復for(let i = startIndex; i <= 9; i++){//取i這個值path.push(i);backtracking(k, n, path, curSum + i, i + 1, res);//回溯path.pop();}
}
17. 電話號碼的字母組合就是組合的思路
/*** @param {string} digits* @return {string[]}*/
var letterCombinations = function(digits) {//dict[i]表示一個選擇let dict = [[], [], ['a','b','c'], ['d', 'e','f'], ['g','h','i'], ['j','k','l'], ['m','n','o'], ['p','q','r','s'], ['t','u','v'], ['w','x','y','z']];let res = [];let k = digits.length;//表示選擇k個字符let digitsArr = digits.split('').map(Number);backtracking(k, 0, "", res, digitsArr, dict);console.log(digitsArr);return res;
};//1.字符串 2 3
//返回dict[2]和dict[3]中可能的字母組合
//迭代k次，依此從dict[2]、dict[3]中選一個數
// 2 3 如何得到，在digitsArr數組中,用參數cur Nnum表示//k表示需要選擇的字母的個數
//curNum表示當前選擇的是哪一個數字對應的字符
//因為curNum要在digitsArr數組中取，所以用curNumIndex，這樣curNum = digitsArr[curNumIndex]
function backtracking(k, curNumIndex, str, res, digitsArr, dict){if(k === 0) return;//找到滿足條件的組合,數量到了if(str.length === k){res.push(str);return;}//從dict[num]中選取一個字符let curNum = digitsArr[curNumIndex];let curDict = dict[curNum];for(let i = 0; i < curDict.length; i++){//依此從dict[curNum]中選取一個字符//選下一個字符backtracking(k, curNumIndex + 1, str + curDict[i], res, digitsArr, dict);}
}
)
