day-25 代码随想录算法训练营（19）回溯part02

216.组合总和|||

思路：和上题一样，差别在于多了总和，但是数字局限在1-9

17.电话号码的字母组合

思路：先纵向遍历第i位电话号码对于的字符串，再横向递归遍历下一位电话号码

93.复原IP地址

画图分析：

 思路一：

先横向遍历，限制遍历数最大为3（因为IP值最多为三位），并且起始位+3要小于字符串长度；

• 判断当前切的字符串是否满足IP值，不满足的话下一个；

然后纵向递归，判断当前切的第几刀

• 如果当前切的第四刀（以1开始，相当于分成四份），则进行判断添加，作为终止条件
• 如果当前还没切到第四刀，则继续横向遍历

最后回溯，直接用resize覆盖掉当前遍历添加字符串的长度

class Solution {
public:vector<string>res;string mid;void backtrace(const string& s,int start,int curb){//start是开始的位置 curb是切割的次数if(curb==4){//cout<<123;if(s.size()-start>3) return;string mids=s.substr(start,s.size()-1);if(judge(mids)){mid+=mids;res.push_back(mid);mid.resize(mid.size()-mids.size());//回溯（覆盖当前添加的字符串）} return;   }for(int i=1;i<=3;i++){//横向遍历//cout<<i;if(start+i>s.size())//剩下的大于需要分配的break;string s1=s.substr(start,i);//第if(!judge(s1)) continue;mid+=s1;mid+=".";backtrace(s,start+i,curb+1);//纵向递归//cout<<mid;//回溯覆盖mid.resize(mid.size()-s1.size()-1);}}bool judge(string s){if(s.empty()) return false;if(s.size()>1 && s[0]=='0') return false;//排除0开头的字符串int num=stoi(s);return num>=0 && num<=255;}vector<string> restoreIpAddresses(string s) {backtrace(s,0,1);return res;}
};