LeetCode 刷题 （九）算法入门–回溯
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路：
如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；
回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
为什么说是在一棵树上的深度优先遍历呢？比如说，你现在要解决一个问题，这个问题被分为了若干的步骤，对于每一个步骤都有多个方法到下一个步骤。（听君一席话，就是一席话，嘿嘿嘿！！）。就是说我们么一个步骤的选择都是可以返回来更换的。
就拿本题来说：
比如说给了4和3这两个数据；我们要从1,2,3,4,这4个数里面取3个数。很容易分析出来：当我们第一个数取1的时候，第二个数可以去2,3,4,.........。一次推下去。我们会得到一棵一棵的树。样子就是这个样子（这个不是我画的，我去LeetCode的题解上找到哈哈哈哈！！）
想明白这个过程，那我们的解题办法就来了。对于[1 n]里面的每一个数，在最后选择的k个数里面的只有两种状态，要么它在，要么它不在。所以我们只需要去遍历这n个数，然后用一个数组temp把放入最后结果的数记录下来。由于我们是从小到大遍历，所以当我们把当前元素在最后结果里面的记录完以后，后面再记录的结果就不会再包含当前元素了。
class Solution {
public:
//temp 用来存放每一个可能的结果
vector<int> temp;
//最终结果
vector<vector<int>> ans;
//深度优先遍历
void dfs(int cur, int n, int k) {
// 剪枝：当遍历到底cur个数是，如果temp的元素个数s+剩余元素个数t<k时，就不满足条件了
if (temp.size() + (n - cur + 1) < k) {
return;
}
// temp中元素个数达到k，表示深度优先遍历到达最深处了。此时需要回溯了。
if (temp.size() == k) {
ans.push_back(temp);
return;
}
// 选择当前位置，加入temp
temp.push_back(cur);
dfs(cur + 1, n, k);
// 不选择当前位置，从temp里面删除
temp.pop_back();
dfs(cur + 1, n, k);
}
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
};思路：通过上一题，这一题理解起来就更方便了。全部排列顺序，就是上面的那个图，第二次先选择了2以后还可以继续选择1；所以我们只需要把每次选取的元素交换到数组左边，这样就可以和上一题的流程一样了，不过记住记住排列的时候，未选择的元素都可以来占当前cur的位置，由于我们将未选择的元素都交换到cur的右边，所以从cur遍历一遍就可以了。就是这么简单，k默认为n就可以了。
class Solution {
public:
void dfs(vector<vector<int>>& res, vector<int>& output, int cur, int len){
// 所有数都填完了
if (cur == len) {
res.emplace_back(output);
return;
}
//这里每一个数组右边的数都可以当做第cur个元素
for (int i = cur; i < len; ++i) {
// 动态维护数组，将未选取的元素交换到数组右边
swap(output[i], output[cur]);
// 继续递归填下一个数
dfs(res, output, cur + 1, len);
// 撤销交换操作
swap(output[i], output[cur]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
dfs(res, nums, 0, (int)nums.size());
return res;
}
};给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
思路： 注意理解题目要求，题目是说每个子母可以进行大小写变换，但是没有说可以改变位置哦。
class Solution {
public:
void dfs(vector<string> &res,int cur,string &s,int len){
//数字不变
while(cur<len&&s[cur] >= '0' && s[cur] <= '9')
cur++;
if(cur == len){
res.emplace_back(s);
return ;
}
//子母转变大小写
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
//子母不转变大小写
if(s[cur]>='a'&&s[cur]<='z')
s[cur] = toupper(s[cur]);
else
s[cur] = tolower(s[cur]);
dfs(res,cur+1,s,len);
}
vector<string> letterCasePermutation(string s) {
vector<string> res;
int len = s.length();
dfs(res,0,s,len);
return res;
}
};芜湖~~~~~~~~~