代码随想录算法训练营第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);
}
}