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 combinationlet path [];//store the solutiionslet 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 idxpath.push(char);//run backtrack functionbacktrack(idx 1);//undo choicepath.pop();}