leetcode|递归回溯的几个小题目递归回溯|c++

感觉这几个回溯的题目思路都蛮简单，放一个简单模板
if（得到一个解）
{
存入答案
返回
}
if(无法得到解）
{
返回
}
if（数据可行）
{
存入数据
递归执行下一层
弹出刚存入的数据
递归执行下一层
}

组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[ [2,4], [3,4],[2,3],[1,2], [1,3],[1,4],]

【leetcode|递归回溯的几个小题目】思路
从第一个位置开始放，对于每个数，我们可以选择放入或者不放入，当放的数量到k的时候，就保留下结果。

class Solution { public: vector> ans; vector temp; void bfs(int n,int k,int m) { //数组中和接下来的数不够k时，不能拼成，返回 if(temp.size()+(n-m+1)> combine(int n, int k) { bfs(n,k,1); return ans; } };

全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路
可惜这个题是vector类型的数组，不能用next_permutation，不然直接小到大排序在next_permutation就完事了。
开始递归回溯的思路，还是从第一个位置开始放，每个位置放的元素可以是nums中的任意一个元素，但是同一个数组方案中不能存在相同的元素。因此我用了一个无序表unordered_set来去重，（官方用了一个更优秀的方法来降低空间复杂度，等下放在后面）。当放到第nums.size()个元素时，可以将这个方案存入答案中。

class Solution { public: vector> ans; vector temp; //去重 unordered_set book; void dfs(int cur,vector&nums) { //放完了 if(cur==nums.size()) { ans.push_back(temp); }for(int i=0; i> permute(vector& nums) { dfs(0,nums); return ans; } };

class Solution { public: void backtrack(vector>& res, vector& output, int first, int len){ // 所有数都填完了 if (first == len) { res.emplace_back(output); return; } for (int i = first; i < len; ++i) { // 动态维护数组 swap(output[i], output[first]); // 继续递归填下一个数 backtrack(res, output, first + 1, len); // 撤销操作 swap(output[i], output[first]); } } vector> permute(vector& nums) { vector > res; backtrack(res, nums, 0, (int)nums.size()); return res; } }; 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

字母大小写全排列
给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回所有可能得到的字符串集合。以任意顺序返回输出。
示例 1：
输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

思路
对于每个字母的，有两种选择，可以将他改为大写，也可以改为小写
然后判断下一个字母，如果是数字的话，则直接判断下一个字母

class Solution { public: vector> ans; void bfs(string &s,int cur) { //执行完毕，插入结果 if(cur==s.length()) { ans.push_back(s); }//处理数字 if(s[cur]>='0'&&s[cur]<='9') { bfs(s,cur+1); }//处理字母 if((s[cur]>='A'&&s[cur]<='Z')||(s[cur]>='a'&&s[cur]<='z')) { s[cur]=tolower(s[cur]); bfs(s,cur+1); s[cur]=toupper(s[cur]); bfs(s,cur+1); } } vector> letterCasePermutation(string s) { bfs(s,0); return ans; } };