代码随想录算法训练营第25天|回溯

回溯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);}
}