切割与子集
切割
切割问题类似于组合问题，区别在于组合是从给定集合选取单个元素用以组合，而切割问题则是决定给定集合中连续元素块并加以组合。例如对于字符串abcdef
- 组合问题：选取a之后，在bcdef中选取第二个字符，选取 b之后在cdef中选取第三个字符.......
- 切割问题：切割a之后，在bcdef中切割第二段，选取 bc之后再切割第三段......
给出两个leetcode原题加以辅助说明
leetcode131
对于给定的一个字符串，将其分割为一些子串，使得每个子串都是回文串
如何判断纵向遍历即递归的深度：只要判断截取子串的起始位置大于等于母串的整个长度，就说明找到了一种分割方案。而横向遍历的宽度则是由母串的大小决定。
如何剪枝：递归过程中，如果出现切割的一个子串不是回文串，那么就没有继续往下递归的必要。于是可以利用continue跳出该次循环。
其抽象树状结构如图所示：
class Solution{
private:
vector<vector<string>> result;
vector<string> path;//存放回文子串
void backtracking(const string& s,int index){
//起始位置大于s.size()-1,表明已经找到一组回文子串
if(index >= s.size()){
result.push_back(path);
return;
}
for(int i = index;i<s.size();i++){
if(isPalindrome(s,index,i)){ //判断子串是否是回文串
//获取起止索引为index和i的子串
string str = s.substr(index,i-index+1);
path.push_back(str);
}else{
continue;
}
backtracking(s,i+1);//进入下一层for循环，此时起始索引是上一层终止索引加1
path.pop_back();//回溯，清楚本次添加的子串
}
}
bool isPalindrome(const string& s,int start,int end){
//双指针法判断是否为回文串
bool flag = true;
while(end >= start){
if(s[start]!=s[end]){
flag = false;
break;
}
end --;
start ++;
}
return flag;
}
public:
vector<vector<string>> partition(string s){
backtracking(s,0);
return result;
}
};
考虑其时间复杂度，设n为字符串长度，最坏情况是是字符串s有 n个相同的字符，任何一种划分均满足要求，长度为n的字符串的划分数为\(2^{n-1}\)=\(O(2^n)\), 而每一种划分需要\(O(n)\)的时间，因此时间复杂度为\(O(n*2^n)\).结果的存储需要\(O(n^2)\)的空间。
给定一个只包含数字的字符串s,用以表示一个IP地址，返回所有可能的IP地址。该问题本身也是一个切割问题，即在s 中插入三个"."来分割字符串使之符合IP地址。同时需要判断划分的子段数字的合法性。由于IP地址是四段数字，需要利用pointnum记录插入的"."数
class Solution{
private:
vector<string> result;//记录结果
void backtrack(string& s,int index,int pointnum){
if(pointnum == 3){//此时字符串已经分割为四段
//判断第四段子串的合法性
if(isvalid(s,index,s.size()-1)){
result.push_back(s);
}
return;
}
for(int i = index;i<s.size();i++){//i表示终止索引
if(isvalid(s,index,i)){//判断[index,i]是否合法
s.insert(s.begin()+i+1,'.');//第i的后面插入'.'
pointnum ++;
backtrack(s,i+2,pointnum);//由于先前已经插入'.',故下一个子串的起始位置是i+2
pointnum --;//回溯
s.erase(s.begin()+i+1);//回溯删除'.'
}else{
break;//子串不合法，结束当次循环
}
}
}
//判断数字段的合法性
bool isvalid(const string& s, int start, int end){
if(start > end){
return false;
}
if(s[start]=='0'&& start != end){//含前导0不合法
return false;
}
int num = 0;
for(int i = start;i<=end;i++){
if(s[i]>'9'||s[i]<'0'){//遇到非数字字符不合法
return fslae;
}
num = num*10+(s[i]-'0');
if(num>255){//大于255即不合法
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s){
result.clear();
if(s.size()<4||s.szie()>12) return result;//每个数字段至少一位数字至多三位数字
backtrack(s,0,0);
return result;
}
}
复杂度分析：IP地址的每段位数至多为3，递归的每一层最多有三种情况，同时IP地址有四个数字段，对应递归层数为四层，递归本身的时间复杂度为 \(O(3^{4})\),复原出一种满足要求的IP地址为\(O(|s|)\),因此总的时间复杂度是 \(O(|s|\times 3^4)\),递归层数为IP地址的数字段数，因此空间复杂度为\(O(h)\),即递归数的高度
子集
组合和分割问题都是根据题目要求选取合适的叶子节点，而子集问题则是找树的所有结点。子集问题是一种组合问题，因为集合是无序的({1,2}与{2,1}相同)，无序意味着取过的元素不会重复取，回溯时需要循环从startindex开始。对于排列问题，集合有序({1,2}与{2,1}不同)，故for循环从0开始取。
组合问题需要进行适当剪枝从而降低问题的复杂度，而子集问题不需要任何的剪枝，因为子集需要遍历整颗树。重新总结一下：
- 子集是收集树形结构中树的所有节点结果
- 组合、分割问题是收集树形结构中叶子节点的结果
给定一个整数数组num,数组中元素互不相同，返回该数组中所有可能的子集，解集中子集不可重复。
class Solution{
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int index){
result.push_back(path);//无需加终止条件，因为for循环结束也就遍历了整个树的节点
for(int i = index;i<nums.size();i++){
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums){
backtracking(nums,0);
return result;
}
};
时间复杂度：按照每个元素是否出现，一共有\(2^n\)个子集，构造单个子集最多需要\(O(n)\)时间，故时间复杂度为\(O(n\times 2^n)\)
空间复杂度：递归时栈空间代价为\(O(n)\)
给定一个整数数组nums，其中可能包含重复元素，返回该数组所有可能的子集，解集中不能包含重复的子集。
上述集合中不存在重复元素，此问题集合中存在重复元素，即要考虑去重，而去重分为纵向的树枝去重和横向的树层去重，简要分析，应该是树层去重。例如nums = [1,1,2,3,4],nums[0]和剩下四个元素组成各种子集就包含了nums[1]与剩下三个元素组成的各种子集。
class Solution{
private:
vector<vector<int>> result;
vector<int> path;
void backtrack(vector<int>& nums, int index){
result.push_back(path);
for(int i = index;i<nums.size();i++){
if(i>index && nums[i]==nums[i-1]){//树层元素去重
continue;
}
path.push_back(nums[i]);
backtrack(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetWithDup(vector<int>& nums){
sort(nums.begin(),nums.end());//树层去重需要对集合排序
backtrack(nums,0);
return result;
}
};
同样的树层去重思路，但不能利用排序来实现树层去重：
给定一个整数数组nums ，其可能包含重复数字，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。与上述子集问题去重不同的是，该问题不能利用排序实现树层去重，我们可利用哈希表记录每层的元素使用情况，从而实现去重。
class Solution{
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums,int index){
if(path.size()>1){
result.push_back(path);//由于取树的节点，不用加return
}
unordered_set<int> uset; //记录每一层元素便于去重
//uset只记录本层元素是否重复，对于新的一层uset会重新定义
for(int i = index;i<nums.size();i++){
//若子序列并不递增或者当前元素已重复，跳过当前循环
if(!path.empty()&&nums[i]<path.back()
||uset.find(nums[i])!=uset.end()){
continue;
}
path.push_back(nums[i]);
uset.insert(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums){
backtracking(nums,0);
return result;
}
};