代码随想录算法训练营第二十八天|93.复原IP地址 、78.子集 、90.子集II

93.复原IP地址 

回溯三部曲

递归参数

startIndex pointNum,记录添加逗点的数量

递归终止条件

pointNum表示逗点数量,pointNum为3说明字符串分成了4段

单层搜索的逻辑

在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环

然后就是递归和回溯的过程:

递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.),同时记录分割符的数量pointNum 要 +1。

回溯的时候,就将刚刚加入的分隔符. 删掉就可以了,pointNum也要-1

判断子串是否合法

最后就是在写一个判断段位是否是有效段位了。

主要考虑到如下三点:

段位以0为开头的数字不合法

段位里有非正整数字符不合法

段位如果大于255了不合法



78.子集 

回溯三部曲

递归函数参数

全局变量数组path为子集收集元素,二维数组result存放子集组合。(也可以放到递归函数参数里)

递归函数参数需要startIndex

不需要加终止条件,因为startIndex >= nums.size(),本层for循环结束

单层搜索逻辑

求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树


90.子集II  

和昨天的去重类似 树层去重

voidbacktracking(vector<int>&nums,intstartIndex,vector<bool>&used){result.push_back(path);for(inti=startIndex;i<nums.size();i++){// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过// used[i - 1] == false,说明同一树层candidates[i - 1]使用过// 而我们要对同一树层使用过的元素进行跳过if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,i+1,used);used[i]=false;path.pop_back();}}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容