本篇文章是关于leetcode的三道递归/回溯问题的探究，分别是“组合”“全排列”“字母大小写全排列”三个问题。
（1）组合
给定两个整数?n?和?k，返回范围?[1, n]?中所有可能的?k?个数的组合可以按?任何顺序?返回答案。
?看到本题，大多数人想到的是先使用暴力for循环来遍历这个数组，但是发现当所给的n和k足够大时，就会嵌套太多的for循环，不利于我们的解题。此时，遇到嵌套层数过多的情况，我们要选择回溯法递归来解决此类问题，我们可以将回溯法解决问题抽象为树类的树形结构来解决，我们将此类为题化成树形结构来解决，如图所示：
可以发现出，1，2，3，4依次取数，当前面取过的数字以后，后面取的数字就不能与之成为组合，每次选的元素都会变化，当我们搜寻到这棵树的叶子结点时，就能找到所有的集合。
下面写出我们的代码：
class Solution {
public :
//创建一个符合条件结果集合的数组
vector < vector < int > res;
//创建一个用来存放符合条件结果的数组
vector < int > temp;
//主函数
vector < vector < int >> combine ( int n, int k)
{
//从第一个数开始递归
dfs ( temp , 1 , n);
return res;
}
//dfs函数进行递归
void dfs ( vector < int > & temp, int start, int n, int k)
{
//递归终止条件：如果temp数组装满了k个数字，则返回并将temp数组装入到res数组中
if( temp.size () == k )
{
res.push_back ( temp );
return;
}
for( int i = start; i <= n ; i++)
{
//处理该结点
temp.push_back ( i );
//继续递归下一个结点
dfs ( temp, start+1 , n , k);
//回溯，一定要恢复到先前的状态，撤销处理的结点
temp.pop_back ();
}
}
};
?通过观察发现，图中? for( int i = start; i <= n ; i++)处存在浪费的情形。举例说明，假如给定的n是4，k给定的值是3时，我们发现当i取值为2时，i满足条件2<=4，但是无论如何取值，则永远无法在2这个位置找到3个数的组合。
我们再次举出例子来找出规律，当n=4，k=3时：
temp.size() = 0 时还需要3个数构成组合，最后3个数为{2, 3, 4}，故此时至多应遍历到2
temp.size() = 1 时还需要2个数构成组合，最后2个数为{3, 4}，故此时至多应遍历到3
temp.size() = 2 时还需要1个数构成组合，最后1个数为{4}，故此时至多应遍历到4
我们可以找出规律，最后的要遍历的数字和数组的当前元素个数和n、k的值有关系，即
lastnum=n-(k-temp.size())+1;
所以我们可以对上述代码段进行剪枝优化，来降低代码的复杂度。
class Solution {
public :
//创建一个符合条件结果集合的数组
vector < vector < int > res;
//创建一个用来存放符合条件结果的数组
vector < int > temp;
//主函数
vector < vector < int >> combine ( int n, int k)
{
//从第一个数开始递归
dfs ( temp , 1 , n);
return res;
}
//dfs函数进行递归
void dfs ( vector < int > & temp, int start, int n, int k)
{
//递归终止条件：如果temp数组装满了k个数字，则返回并将temp数组装入到res数组中
if( temp.size () == k )
{
res.push_back ( temp );
return;
}
for( int i = start; i <= n - ( k - temp.size () ); i++)
{
//处理该结点
temp.push_back ( i );
//继续递归下一个结点
dfs ( temp, start + 1 , n , k);
//回溯，一定要恢复到先前的状态，撤销处理的结点
temp.pop_back ();
}
}
};?
(2)全排列
给定一个不含重复数字的数组?nums?，返回其?所有可能的全排列?。你可以?按任意顺序?返回答案。
此题与上题有异曲同工之妙，都是需要将数组中的数字进行组合并且进行返回。但是本题是给定一个数组，让你返回不同的排列顺序。?每一个数组中都存在三个元素，但是每个数组不允许有重复的元素出现，所以我们第一时间就是想到了回溯法。回溯法允许试错，发现下一步得不到答案时，就会返回上一步再次寻找问题的答案，重点是回退这一步骤，和深度优先遍历算法很类似，我们同样也画出树形图来观察。
如果取了1，2，3中的一个数字后，怎么保证下次取值避开这个值呢，我们想到可以使用状态数组bool类型来记录是否取到该值，具体代码如下：
?
class Solution {
public :
//创建一个符合条件结果集合的数组
vector < vector < int > res;
//创建一个用来存放符合条件结果的数组
vector < int > temp;
//创建一个状态数组来判断该结点是否取过
vector < bool > status;
//存放题目给定数组的元素个数
int n;
//主函数
vector < vector < int >> permute ( vector < int > &nums)
{
//获取数组的大小
n = nums.size ();
//重置状态函数为未读状态
status.resize ( n, false);
//调用函数
dfs ( nums );
return res;
}
//dfs函数进行递归
void dfs ( vector < int > & nums)
{
//递归终止条件：如果temp数组装满了n个数字，则返回并将temp数组装入到res数组中
if( temp.size () == n )
{
res.push_back ( temp );
return;
}
for( int i = 0; i < n; i++)
{
//如果没有访问，则处理该结点
if( !status [i])
{
//则访问，并且标记为true
status[i] = true;
temp.push_back ( i );
dfs ( nums );
//回溯，一定要恢复到先前的状态，撤销处理的结点
temp.pop_back ();
//将结点设置为未访问状态
status[i] = false;
}
}
}
};(3)字母大小写全排列
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
?本题同样是要求将给定字符串组合排列得到新的字符串的集合，我们同样可以采用回溯算法，下面给出相应的代码：
class Solution {
public:
//返回结果的字符串集合
vector < string > res;
//主函数
vector < string > letterCasePermutation ( string s )
{
int n = s.size ();
//将原串加入到结果集合中
res.push_back ( s );
dfs ( s, 0, n );
return res;
}
//子函数
void dfs ( string &s, int start, int n)
{
//从第一个字符开始遍历
for( int i =s tart; i < n; i++)
{
//当前字符为小写字母时将其转化为大写字母
if( s[i] >= 'a' && s[i] <= 'z')
{
s[i] = s[i] + ( 'A'-'a' );
//加入到数组中
res.push_back ( s );
//开始递归
dfs (s, i + 1, n);
//回溯状态
s[i] = s[i] - ( 'A' - 'a' );
}
//当前字符为大写字母时，转化为小写字母
else if( s[i] >= 'A' && s[i] <= 'Z' )
{
s[i] = s[i] - ( 'A' - 'a' );
res.push_back ( s );
dfs ( s, i + 1, n );
s[i] = s[i] + ( 'A' - 'a' );
}
}
}
};以上三题都是回溯的经典题型，其实可以找到规律，我们可以把解题步骤分为四部：找到递归终止条件-->满足递归条件式->开始递归->恢复现场 这四部，还需多多练习，掌握思想才是王道！