17.一个电话号码的字母组合回溯(backtrack)解法

基本思想：实现回溯法的模版如下：

// for (let choices of choices) {

// if (isValid(state, choice)) {

// makeChoice(state, choice);

// backtrack(state, choice, res);

// undoChoice(state, choice);

// }

// }

var letterCombinations = function(digits) {

//record current combination

let path = [];

//store the solutiions

let res = [];

const map = new Map([

['2', "abc"],

['3', "def"],

['4', "ghi"],

['5', "jkl"],

['6', "mno"],

['7', "pqrs"],

['8', "tuv"],

['9', "wxyz"],

])

backtrack(0);

return res;

function backtrack(idx) {

if (!digits.length) return [];

//回溯终止条件

if (path.length === digits.length) {

//path是数组，我们只要数组里的元素，join方法1.连接数组中元素2.输出字符串

res.push(path.join(''));

return;

}

//idx指向当前要做出选择的号码

let letters = map.get(digits[idx]);

for (char of letters) {

//make choice, then increase the idx

path.push(char);

//run backtrack function

backtrack(idx + 1);

//undo choice

path.pop();

}