- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯法
使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。
如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
究其本质，其实就是枚举。
如果没有更多的数字需要被输入，说明当前的组合已经产生。
如果还有数字需要被输入：
- 遍历下一个数字所对应的所有映射的字母。
- 将当前的字母添加到组合最后，也就是
str + tmp[r]。
constletterCombinations=function(digits){if(!digits){return[]}constlen=digits.lengthconstmap=newMap()map.set('2','abc')map.set('3','def')map.set('4','ghi')map.set('5','jkl')map.set('6','mno')map.set('7','pqrs')map.set('8','tuv')map.set('9','wxyz')constresult=[]functiongenerate(i,str){if(i===len){result.push(str)return}consttmp=map.get(digits[i])for(letr=0;r<tmp.length;r++){generate(i+1,str+tmp[r])}}generate(0,'')returnresult}
N+M是输入数字的总数
- 时间复杂度：O(3^N * 4^M)
- 空间复杂度：O(3^N * 4^M)