1.电话号码的任意组合
解题思路：这是一道典型的DFS题型，需要遍历所有情况，针对DFS主要考虑三点即可。一是截止条件；二是遍历候选节点；三是对候选节点进行筛选
这道题dfs函数里的截止条件无疑就是字符串长度满足digits.size()时即可插入到res中（res是我们返回的结果),并且跳出当前递归，候选节点即是数字所代表的字符
具体代码入下：
class Solution {
public:
vectorp{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(vector&res,int l,string str,string s)
{if(l==str.size())//截止条件
{res.push_back(s);
return;
}
for(auto i:p[str[l]-'0'])//遍历候选节点
{s.push_back(i);
dfs(res,l+1,str,s);
s.pop_back();//每次完成一次插入后要删掉最后一个字符
}
}
vector letterCombinations(string digits) {
vectorres;
if(digits=="") return res;
string s;
dfs(res,0,digits,s);
return res;
}
};
2.组数总和
解题思路：这道题最重要的也是要找到截止条件，我设立了变量m来计算每个组合的累加值，当数值大于等于目标值时，就可以推出当前递归了，不过退出前需要判断m是不是刚好
等于目标值，如果刚好相等。并且该组合在解集中不存在就可以存入解集。
代码如下：
class Solution {
public:
void dfs(vectorff,vector>& res,vectorp,int m)
{int n=accumulate(p.begin(),p.end(),0);
if(n>=m)//截止条件
{
if(n==m) //该组合累加值刚好==target
{ sort(p.begin(),p.end());
auto it=find(res.begin(), res.end( ),p);//组合在解集中不存在
if(it==res.end())
res.push_back(p);
}
return;
}
for(int i=0;i//遍历所有解集
{
p.push_back(ff[i]);
dfs(ff,res,p,m);
p.pop_back();
}
}
vector> combinationSum(vector& candidates, int target) {
vector>res;
vectorp;
dfs(candidates,res,p,target);
return res;
}
};
3.全排列
解题思路：这道题的截止条件是组合个数，当组合个数等于num.size()时，就可以把结果插入到解集了。注意nums中的数字在同一组合中不能重复使用，
这就需要对候选节点进行筛选，具体的筛选过程和代码如下所示：
class Solution {
public:
void dfs(vectornum,vector>&res,vectorp,vectorf)
{if(p.size()==num.size())//截止条件，组合长度=nums.size()
{res.push_back(p);
return;
}
for(int i=0;i
{ if(f[i]!=true) //只有当f[i]为flase时，才能存入组合
{p.push_back(num[i]);
f[i]=true; //存完后要将f[i]设为true
dfs(num,res,p,f);
f[i]=false; //每进行一次递归都要使发f[i]变为true，并且删除组合的最后一个数字（因为后面的组合要继续使用)
p.pop_back();
}
}
}
vector> permute(vector& nums) {
vector>res;
vectorp;
vectorf(nums.size());//把f数组作为筛选条件，初始化为flase
dfs(nums,res,p,f);
return res;
}
};
4.全排列2
解题思路：这道题是上题的变种，但是这道题的nums数组可能是重复的，因此会产生相同的组合。所以需要在上一道题的基础上对筛选条件进行改进。
具体的改进措施是建立一ff数组专门存放nums中数字的个数。每次进入递归前将ff数组中对应的值-1。并且在每次递归前判断对应位置的值是否大于0，
如果大于才能进入递归
代码如下：
class Solution {
public:
void dfs(vectorp,vectorpp,vectorppp,vector>&res,int m)
{if(ppp.size()==m)//截止条件
{res.push_back(ppp);
return;
}
for(int i=0;i//遍历可能的结点
{
if(pp[i]>0)//只有该数值对应的个数大于0才能插入组合
{
ppp.push_back(p[i]);
pp[i]--; //将该数字对应的个数值-1；
dfs(p,pp,ppp,res,m);
pp[i]++;//j每结束一次递归要将该数字对应的值+1，并且删除组合尾元素（后面组合需要用）
ppp.pop_back();
}
}
}
vector> permuteUnique(vector& nums) {
maps;
for(auto i:nums) s[i]++;
vectorf;
vectorff;
vectorfff;
vector>res;
for(auto i:s)
{
f.push_back(i.first);
ff.push_back(i.second);
}
dfs(f,ff,fff,res,nums.size());
return res;
}
};
5.括号生成
解题思路：先判断截止条件，当字符串中'('个数和’)'个数都为3时就可以把该字符串插入到结果中。接下来判断筛选条件，用两个数组记录字符串中'('个数和'('个数，
当符串中'(‘和')'个数相同时，只能把'('放入字符串，否则'('和')'都能放入字符串
具体代码如下图所示
class Solution {
public:
void dfs(vector&res,string p,vector&f)
{if(f[0]==0&&f[1]==0)//截止条件，f[0]和f[1]分别存放左右括号数量，当f[0]和f[1]都为0时，截止
{
res.push_back(p);
return;
}
if(f[0]>0)//只要左括号个数没到达n个，左括号就可以插入到字符串中
{ f[0]--;
p+='(';
dfs(res,p,f);
f[0]++;
p.pop_back();
}
if(f[1]>0&&f[1]!=f[0])//只有左右括号个数不相同时才能将右括号插入到字符串
{ f[1]--;
p+=')';
dfs(res,p,f);
f[1]++;
p.pop_back();
}
}
vector generateParenthesis(int n) {
vectorres;
vectorf{n,n};
string p="";
dfs(res,p,f);
return res;
}
};
6.路径总和||
解题思路：首先找到截止条件，这道题很明显，每次递归到叶子节点后就可以退出递归。即找到叶子结点就是截止条件的关键，
所以这道题的截止条件就是在不断的dfs中总会出现一个结点，该结点的左右孩子都为空，只要找到这个结点，就可以判断从根节点到
该节点的数值总和是否等于目标值，如果相等就可以将该组合插入到结果中。
具体代码如下：
class Solution {
public:
void dfs( TreeNode *node,vector>&res,vectorp,int target)
{
if(node->left==nullptr&&node->right==nullptr)//截止条件，找到叶子节点
{
if(target==0) res.push_back(p);//判断根节点到叶子节点的值是否等于目标值，如果相等则将该组合插入到结果中
return;
}
if(node->left!=nullptr)//筛选条件：判断结点的左孩子是否为空，如果不为空，将该左孩子的值插入到该组合中，并且进入递归
{ p.push_back(node->left->val);
target=target-node->left->val;//target为0时就可以将该组合插入结果数组中
dfs(node->left,res,p,target);
p.pop_back();
target+=node->left->val;
}
if(node->right!=nullptr)//筛选条件：判断结点的右孩子是否为空，如果不为空，将该右孩子的值插入到该组合中，并且进入递归
{ p.push_back(node->right->val);
target=target-node->right->val;//target为0时就可以将该组合插入结果数组中
dfs(node->right,res,p,target);
p.pop_back();
target+=node->right->val;
}
}
vector> pathSum(TreeNode* root, int targetSum) {
vector>res;
if(root==nullptr) return res;
vectorp;
p.push_back(root->val);
int target=targetSum-root->val;
dfs(root,res,p,target);
return res;
}
};
7.求根节点到叶子节点数字之和
解题思路：这道题的截止条件和筛选条件和上道题几乎一样，这里就不多做解释了，直接放代码：
class Solution {
public:
void dfs(int &res,int s,TreeNode *node)
{if(node->left==nullptr&&node->right==nullptr)//截止条件
{ res+=s;
return;
}
else
{
if(node->left!=nullptr)//筛选条件
{ s=10*s+node->left->val;
dfs(res,s,node->left);
s=(s-node->left->val)/10;
}
if(node->right!=nullptr)//筛选条件
{s=10*s+node->right->val;
dfs(res,s,node->right);
s=(s-node->right->val)/10;
}
}
}
int sumNumbers(TreeNode* root) {
int res=0;
int s=root->val;
dfs(res,s,root);
return res;
}
};
8.岛屿数量
解题思路：这种二维数组的dfs题其实和树的dfs题很像，只不过树是左右孩子两种转移方法。而二维数组中的每个数，都可以
上下左右四个方向移动，所以有四个判断条件，只要满足这四个条件，就可以继续向下递归。具体代码如下图所示
class Solution {
public:
void dfs(vector>&g,int i,int j)
{
if(i-1>=0&&g[i-1][j]=='1') {g[i-1][j]='0';dfs(g,i-1,j);}
if(i+1
if(j-1>=0&&g[i][j-1]=='1') {g[i][j-1]='0';dfs(g,i,j-1);}
if(j+1
}
int numIslands(vector>& grid) {
int n = grid.size();
if (!n) return 0;
int res=0;
int m=grid[0].size();
for(int i=0;i
{
for(int j=0;j
{
if(grid[i][j]=='1')
{
dfs(grid,i,j);
res++;
}
}
}
return res;
}
};