131. 分割回文串
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
思路分析
本题这涉及到两个关键问题：
切割问题，有不同的切割方式
判断回文
切割问题类似组合问题
对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。
⭐️⭐️⭐️ 注意: 组合的index是选取的组合数的下标位置.而切割的index是切割位置数的index,但是实际位置却是index+1,所以下一次传入的将是index+1.
树形结构图
如图所示 index=0,切割位置1,下一轮传入的也是1,当所有的切割完毕,下一次传入的是 arr.size().这个将作为递归的结束条件
算法设计
确定递归函数参数和返回值
参数:递归的字符串s,每层递归的startIndex
全局变量path存放切割后的回文子串,result存放结果集,所以不需要返回值.
确定递归结束条件
如果起始位置已经>=s的大小，说明已经找到了一组分割方案了,结束递归即可
确定单层递归逻辑
首先判断这个子串[startIndex,i]是不是回文，如果是回文，就加入在vector<string> path中,然后递归,完毕后回溯. 如果不是则 i++ 判断下一个…
回文串的判断我们可以使用双指针法或者反转字符串进行比较的方法
参考代码
#include<bits/stdc++.h> using namespace std; vector<string> path; vector<vector<string>> result; bool isHuiWen(string& str,int i,int j){//判断是否是回文串 for(;i<j;i++,j--) { if(str[i]!=str[j]){ return false; } } return true; } void backtracking(string& s,int startIndex){ //结束条件 if(startIndex>=s.size()){ result.push_back(path); return; } for(int i = startIndex; i < s.size();i++){ if(isHuiWen(s,startIndex,i)){ path.push_back(s.substr(startIndex,i-startIndex+1)); }else{ continue; } backtracking(s,i+1); path.pop_back(); } } vector<vector<string>> partition(string s) { backtracking(s,0); return result; }
93. 复原 IP 地址
题目描述
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
思路分析
这个题和上文的分割回文串很相似,先截取,再判断,符合则进行继续递归
⭐️⭐️⭐️ 回溯三部曲
确定递归参数和返回值
参数:目标串s,搜索的起始位置startIndex,添加 .的数量pointNum
返回值:因为使用了全局变量保存结果,所以无需返回值.
确定递归结束条件
本题虽然说是用三个.做分割,但是也要判断最后一段是否是合格串
确定单层递归逻辑
先判断是否是合格串,如果是则添加点. 然后递归,回溯,进行下一轮循环. 如果不是,则直接 i++…
💥💥💥合格串需要满足的条件
段位以0为开头的数字不合法
段位里有非正整数字符不合法
段位如果大于255了不合法
#include<bits/stdc++.h> using namespace std; vector<string> result; //本题和上题非常相似,只是判断是否是IP这个过程复杂了些 void backtracking(string& s,int startIndex,int pointNum) { if(pointNum == 3) { if(isValid(s,startIndex,s.size()-1)) { result.push_back(s); } return; } for(int i = startIndex; i < s.size(); i++) {//i子串结束位置的索引 [startIndex,i] if(isValid(s,startIndex,i)) { s.insert(s.begin()+i+1,'.'); backtracking(s,i+2,pointNum+1); s.erase(s.begin()+i+1); } else { continue; } } } bool isValid(string& s,int begin,int end) { if(begin > end) { //空字符 return false; } if(s[begin]=='0'&&begin != end) { //1.是否以‘0’开头 return false; } int num = 0; for(int i = begin; i<=end; i++) { if(s[i] < '0' || s[i]>'9') { //3.是否不是数字 return false; } num = num*10 + s[i]-'0' ;//注意不能写成 num *=10 + s[i]-'0' if(num > 255) { //2.数字大小是否 》=0 && 《=255 return false; } } return true; } vector<string> restoreIpAddresses(string s) { backtracking(s,0,0); return result; }
78. 子集
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
思路分析
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
回溯三部曲
确定递归参数和返回值
递归参数:需要遍历的数组 vector<int> &nums,每层遍历的起始下标startIndex .
返回值:由于定义全局变量来保存最终结果集以及单一结果,所以并不需要返回值.
确定结束条件
由于这次是寻找所有的组合,所以并不需要结束条件.没递归一层就把对应的结果放入到结果集中.
确定单层递归逻辑
将当前组合数加入单一结果集,递归,回来后进行回溯.进行下一次循环.
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> path; vector<vector<int>> result; void backtracing(vector<int>& nums,int startIndex){ result.push_back(path); for(int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); backtracing(nums,i+1); path.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { backtracing(nums,0); return result; }
90. 子集 II
题目描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
思路分析
这个题的数组nums可能包含重复元素,则需要对树层进行去重. 目前我们有三种去重方法:利用vector<bool> used , 利用startIndex, 利用ordered_set<int> ,下面我们将逐一进行演示.
用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
本题不再分析递归三部曲了,关键部分将添加相关注释.
参考代码
#include<bits/stdc++.h> using namespace std; //https://leetcode.cn/problems/subsets-ii vector<int> path; vector<vector<int>> result; //其实相比上题只是多了个同层去重的步骤 void backtracing(vector<int>& nums,int startIndex,vector<bool>& used){ result.push_back(path); for(int i = startIndex; i < nums.size(); i++){ if(i>=1 && used[i-1]== false && nums[i-1]==nums[i]){//树层去重 continue; } used[i] = true; path.push_back(nums[i]); backtracing(nums,i+1,used); used[i] = false; path.pop_back(); } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<bool> used(nums.size(),0); sort(nums.begin(),nums.end()); backtracing(nums,0,used); return result; }
