一、DFS的框架，必须熟记
void dfs(int k)
{
if(到达终点或者目的地）
{
输出问题解或者解得方案数+1；
}
for(int i = 0;i<="可扩展状态总数";i++)
{
按照规则，产生新的状态；
if(判断新状态是否合法）
{
保存合法结果;
dfs(k+1);
恢复现场，回溯；//可以没有，根据情况来定
}
}
}
int main()
{
.....
dfs(k);
回溯；//可选
return 0;
}
回溯法是DFS的一种搜索策略
回溯法可以解决如下几种问题：
排列问题：N个数按照一定规则全排列，有几种排列方式
组合问题：如何按照一定规则在N个数中找出K个数的集合
切割问题：一字符串按照一定规则切割，有几种切割方式
子集问题：一个N个数的集合中有多少符合条件的子集
棋盘问题：N皇后、数独等问题
二、切割问题
[例1、切割回文子串]
(https://www.luogu.com.cn/problem/T239006)
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入格式
一行一个字符串
输出格式
若干行，每行表示一种分割方案，回文串之间用一个空格隔开
输入输出样例
输入
aab
输出
a a b
aa b
【思路】
本题这涉及到两个关键问题：
- 切割问题，有不同的切割?式
- 判断回?
我们来分析?下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：
组合问题：选取?个a之后，在bcdef中再去选取第?个，选取b之后在cdef中在选组第三个…。
切割问题：切割?个a之后，在bcdef中再去切割第?段，切割b之后在cdef中在切割第三段…。
所以切割问题，也可以抽象为?颗树形结构，如图：
所以，我们可以参看组合的搜索方式进行。
#include<bits/stdc++.h>
using namespace std;
string ans[105];
string s;
int len;
int x = 0;
bool ishw(int start,int end)//双指针判定回文
{
int i = start,j = end;
for(;i<j;i++,j--)
{
if(s[i]!=s[j]) return false;
}
return true;
}
void dfs(int index)
{
if(index>=len)
{
for(int i = 1;i<=x;i++) cout<<ans[i]<<" ";
cout<<endl;
return;
}
for(int i = index;i<len;i++)
{
if(ishw(index,i))
{
string str = s.substr(index,i-index+1);
ans[++x]=str;
//cout<<ans[x]<<" ";
}
else continue;//不是回文，则跳过，不能省略哦
dfs(i+1);
x--;
}
}
int main()
{
cin>>s;
len = s.size();
//cout<<ishw(0,len-1);
dfs(0);
return 0;
}
例2.复原IP地址
题目描述
给定?个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间?’.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 ?效的 IP 地址。
输入格式
一行只由数字组成的字符串
输出格式
若干行，每行为可行的IP分割方式
输入
25525511135
输出
255.255.11.135
255.255.111.35
说明/提示
0 <= s.length <= 3000 s 仅由数字组成
【解析】
切割问题就可以使?回溯搜索法把所有可能性搜出来。
1、和上一道题目类似，Index?定是需要的，因为不能重复分割，记录下?层递归分割的起始位置。本题我们还需要?个变量point，记录添加逗点的数量。
2、终?条件和回溯算法：分割回?串情况就不同了，本题明确要求只会分成4段，所以不能?切割线切到最后作为终?条件，?是分割的段数作为终?条件。
point表示逗点数量，point为3说明字符串分成了4段了。
然后验证?下第四段是否合法，如果合法就加?到结果集?
3、判定子串是否合法
段位以0为开头的数字不合法
段位?有?正整数字符不合法
段位如果?于255了不合法
【上代码】
#include<bits/stdc++.h>
using namespace std;
string s;
int len,point;
bool isIP(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 false;
num = num * 10 + (s[i] - '0');
if(num > 255) return false;// 如果大于255了不合法
}
return true;
}
void dfs(int index,int point)//index: 搜索的起始位置，point:添加逗点的数量
{
if(point==3)// 逗点数量为3时，分隔结束
{
if(isIP(index,s.size()-1))// 判断第四段子串是否合法，如果合法就输出
{
cout<<s<<endl;
return ;
}
}
for(int i = index;i<s.size();i++)
{
if(isIP(index,i))// 判断 [index,i] 这个区间的子串是否合法
{
s.insert(s.begin()+i+1,'.');
point++;
dfs(i+2,point);// 插入逗点之后下一个子串的起始位置为i+2
point--;
s.erase(s.begin() + i+1); // 回溯删掉逗点
}
else break;
}
}
int main()
{
cin>>s;
len = s.size();
if(len>12) return 0;//减枝
dfs(0,0);
return 0;
}
三、子集问题
如果把 ?集问题、组合问题、分割问题都抽象为?棵树的话，那么组合问题和分割问题都是收集树的叶?节点，??集问题是找树的所有节点！
例3.幂集
题目描述
给定?组不含重复元素的整数数组 nums，返回该数组所有可能的?集（幂集）。
说明：解集不能包含重复的?集。
输入格式
第一行，一个整数n，表示数组的元素个数； 第二行，数组的元素，中间用一个空格隔开
输出格式
若干行，每行为一个子集，注意空集也算哦
输入 #1复制
3
1 2 3
输出
1
1 2
1 2 3
1 3
2
2 3
3
说明/提示
n<=20
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的?集集合。
注意问题：
1、剩余集合为空的时候，就是叶?节点。
那么什么时候剩余集合为空呢？
2、就是startIndex已经?于数组的?度了，就终?了，因为没有元素可取了，代码如下:
其实可以不需要加终?条件，因为startIndex >= nums.size()，本层for循环本来也结束了。
3、求取?集问题，不需要任何剪枝！因为?集就是要遍历整棵树。
【上代码】
#include<bits/stdc++.h>
using namespace std;
int a[105];
int ans[105];
int n;
int x = 0;
void dfs(int index)
{
//if(index==n+1)//不需要终止条件，因为index >= n，本层for循环本来也结束了。
for(int i = 1;i<=x;i++) cout<<ans[i]<<" ";
cout<<endl;
// return ;
for(int i = index;i<=n;i++)
{
ans[++x]=a[i];
dfs(i+1);
x--;
}
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++) cin >>a[i];
dfs(1);
return 0;
}
练习题目
1、自然数的拆分
–视频讲解
2、数的划分NOIP2001
–视频讲解
