个人制作网站工具,个人简历怎么做,wordpress自建邮箱,什么是网络工程师目录 一、组合问题
组合
组合剪枝
组合总和 III编辑
组合总和编辑
组合总和 II
电话号码的字母组合编辑
二、分割问题
分割回文串
复原 IP 地址
三、集合问题
子集
子集 II 非递减子序列
四、排列问题
全排列
全排列 II
五、棋盘问题 N 皇后 课程#x…目录 一、组合问题
组合
组合剪枝
组合总和 III编辑
组合总和编辑
组合总和 II
电话号码的字母组合编辑
二、分割问题
分割回文串
复原 IP 地址
三、集合问题
子集
子集 II 非递减子序列
四、排列问题
全排列
全排列 II
五、棋盘问题 N 皇后 课程 【带你学透回溯算法理论篇| 回溯法精讲】https://www.bilibili.com/video/BV1cy4y167mM?vd_source342079de7c07f82982956aad8662b467 关于回溯算法你该了解这些
组合问题N个数里面按一定规则找出k个数的集合排列问题N个数按一定规则全排列有几种排列方式切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集棋盘问题N皇后解数独等等
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}一、组合问题
组合
class Solution {
public:void backtracking(int pos, vectorint path, vectorvectorint res, int k, int n) {if (path.size()k) {res.push_back(path);return;}for (int i pos;i n1;i) {path.push_back(i);backtracking(i 1, path, res, k, n);path.pop_back();}}vectorvectorint combine(int n, int k) {vectorvectorint res;vectorint path;backtracking(1, path, res, k, n);return res;}
};
组合剪枝 在上面的这个组合的代码实际上我们可以进一步去优化也就是对构造的树进行剪枝的操作。我们可以这么理解已知可以选择走的路径总长度为n在当前的横向遍历节点上已知前面走过路径上长度为size然后总共是需要走的长度为k那么是不是可以说还需要走k-size的长度的路径是吧那也意味着在当前横向遍历的节点长度最起码是从n-(k-size)1开始这个加一是表示字节当前这个节点。 修改的代码如下
class Solution {
public:void backtracking(int pos, vectorint path, vectorvectorint res, int k, int n) {if (path.size()k) {res.push_back(path);return;}for (int i pos;i n - (k - path.size()) 1;i) {path.push_back(i);backtracking(i 1, path, res, k, n);path.pop_back();}}vectorvectorint combine(int n, int k) {vectorvectorint res;vectorint path;backtracking(1, path, res, k, n);return res;}
};
下面三个案例练练手看看。 组合总和 III class Solution {
public:void backtracking(int pos,int sum,int n, int k,vectorint path ,vectorvectorint re){if (sum n path.size() k) {re.push_back(path);return;}if (path.size() k) {return;}for (int i pos;i 9;i) {if (sum i n) {sum i;path.push_back(i);backtracking(i 1, sum, n, k, path, re);sum - i;path.pop_back();}}}vectorvectorint combinationSum3(int k, int n) {vectorvectorint re;vectorint path;int sum 0;backtracking(1, sum, n, k, path, re);return re;}
};
这里可以看到执行的剪枝操作就是当sumi大于目标值n的时候就不执行深度递归操作。 组合总和 class Solution {
public:void backtracking(int pos, int sum, int target, vectorvectorint re, vectorint candidates,vectorint path) {if (sum target) {re.push_back(path);return;}if(poscandidates.size() || sumtarget){return ;}for (int i pos;i candidates.size() sum candidates[i] target;i) {sum candidates[i];path.push_back(candidates[i]);backtracking(i, sum, target, re, candidates, path);sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());vectorvectorint re;vectorint path;backtracking(0, 0, target, re, candidates, path);return re;}
}; 组合总和 II class Solution {
public:void backtracking(int pos,int target, int sum,unordered_mapint, bool used ,vectorint path, vectorint candidates,vectorvectorint re){if (sum target) {re.push_back(path);return;}for (int i pos;i candidates.size() sum candidates[i] target;i) {if(i0 candidates[i]candidates[i-1] used[candidates[i-1]]false){continue;}sum candidates[i];path.push_back(candidates[i]);used[candidates[i]] true;backtracking(i 1, target, sum,used, path, candidates, re);sum - candidates[i];path.pop_back();used[candidates[i]] false;}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());vectorvectorint re;vectorint path;unordered_mapint, bool used;backtracking(0, target, 0, used, path, candidates, re);return re;}
}; 电话号码的字母组合 class Solution {
public:void backtracking(int pos,string path,string digits, vectorstring map, vectorstring res){if (path.size() digits.size() ) {res.push_back(path);return;}int num digits[pos] - 0;for (int i 0;i map[num].size();i) {path.push_back(map[num][i]);backtracking(pos 1, path, digits, map, res);path.pop_back();}}vectorstring letterCombinations(string digits) {vectorstring map {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring res;string path ;if(digits.size() 0)backtracking(0, path, digits, map, res);return res;}
};
二、分割问题 分割回文串 这个切割问题其实类似上面那些组合问题其实就是按照字符串的顺序去进行划分子串组合然后限制条件就是回文串如果是回文串就添加到路径中如果不是回文串就跳过。
class Solution {
public:bool is_huiwen(string s) {int i 0, j s.size()-1;while (i j) {if (s[i] ! s[j]) {return false;}i;j--;}return true;}void backtracking(int pos, vectorstring route, string path, string s, vectorvectorstring res) {if (pos s.size()) {res.push_back(route);route.clear();return;}for (int i pos;i s.size();i) {string temp s.substr(pos,i-pos1);if (is_huiwen(temp)) {route.push_back(temp);backtracking(i 1, route, path, s, res);route.pop_back();}}}vectorvectorstring partition(string s) {vectorvectorstring res;vectorstring route;string path;backtracking(0, route, path, s, res);return res;}
}; 复原 IP 地址 class Solution {
public:bool isvalid(string s) {if(s.empty() || s.size()3){return false;}if (s.size() 1 s[0] 0) {return false;}int num stoi(s);if (num 255 || num0) {return false;}return true;}void backtracking(int pos,int start, string tmp, string s, vectorstring res) {if (pos 3) {string t s.substr(start, s.size() -pos 1);if (isvalid(t)) {tmp t;res.push_back(tmp);}return;}for (int i start;i s.size();i) {string t s.substr(start,i-start1);if (isvalid(t)) {for (int j 0;j t.size();j) {tmp.push_back(t[j]);}tmp.push_back(.);pos;backtracking(pos, i 1, tmp, s, res);for (int j 0;j t.size();j) {tmp.pop_back();}tmp.pop_back();pos--;}}}vectorstring restoreIpAddresses(string s) {vectorstring res;string tmp;backtracking(0,0, tmp, s, res);return res;}
};
三、集合问题 对于子集问题其实跟前面的不同子集是每一个递归的节点都要进行数据的收集而前面的组合问题都是有条件限制的才执行收集的操作比如递归收集数字和为target的组合之类的。 子集 回溯算法求子集问题 class Solution {
public:void backtracking(int start_index, vectorint nums, vectorint path, vectorvectorint res) {res.emplace_back(path);for (int i start_index;i nums.size();i) {path.push_back(nums[i]);backtracking(i 1, nums, path, res);path.pop_back();}}vectorvectorint subsets(vectorint nums) {vectorvectorint res;vectorint path;backtracking(0, nums, path, res);return res;}
}; 子集 II 这个问题其实是组合总和2的一个派生问题本质上是差不多的无法就是需要一个东西来去标记一下使用过的数据避免下次重新去使用。 class Solution {
public:void backtracking(int pos, unordered_mapint, bool used, vectorint nums, vectorint path, vectorvectorint res) {res.emplace_back(path);for (int i pos; i nums.size();i) {if (i 0 nums[i] nums[i - 1] used[nums[i - 1]] false) {continue;}path.push_back(nums[i]);used[nums[i]] true;backtracking(i 1, used, nums, path, res);used[nums[i]] false;path.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint res;vectorint path;unordered_mapint, bool used;backtracking(0, used, nums, path, res);return res;}
}; 非递减子序列 对于这个问题也就是说每一层需要去避免重复使用同一个数字也就是需要在每一个递归节点去创建一个作为标记的哈希表来依次标记已经遍历的节点这里对比前面使用了纵向哈希表是不一样的这个是横向的。 class Solution {
public:void backtracking(int pos,vectorint path, vectorint nums,vectorvectorint res) {if(path.size()2)res.emplace_back(path);if (pos nums.size()) {return;}unordered_mapint, bool used;for (int i pos;i nums.size();i) {if (path.size() 0 path.back() nums[i]) {continue;}if (used[nums[i]]) {continue;}path.push_back(nums[i]);used[nums[i]] true;backtracking(i 1, path, nums,res);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {vectorvectorint res;vectorint path;backtracking(0, path, nums, res);return res;}
};
class Solution {
public:void backtracking(int pos,vectorint path, vectorint nums,vectorvectorint res) {if(path.size()2)res.emplace_back(path);if (pos nums.size()) {return;}int used[201] {0};for (int i pos;i nums.size();i) {if (path.size() 0 path.back() nums[i]) {continue;}if (used[nums[i]100]) {continue;}path.push_back(nums[i]);used[nums[i]100] true;backtracking(i 1, path, nums,res);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {vectorvectorint res;vectorint path;backtracking(0, path, nums, res);return res;}
};
四、排列问题 全排列 class Solution {
public:void backtracking(int pos,unordered_mapint, bool used, vectorint nums, vectorint path, vectorvectorint res) {if (path.size() nums.size()) {res.emplace_back(path);return;}for (int i 0;i nums.size();i) {if (used[nums[i]] false) {used[nums[i]] true;path.push_back(nums[i]);backtracking(i 1, used,nums, path, res);used[nums[i]] false;path.pop_back();}}}vectorvectorint permute(vectorint nums) {vectorvectorint res;vectorint path;unordered_mapint, bool used;backtracking(0,used, nums, path, res);return res;}
}; 全排列 II class Solution {
public:void backtracking(int pos,unordered_mapint, bool map, vectorint nums, vectorint path, vectorvectorint res) {if (path.size() nums.size()){res.emplace_back(path);return;}bool used[21] { false };for (int i 0;i nums.size();i) {if (! used[nums[i]10] !map[i]) {used[nums[i] 10] true;map[i] true;path.push_back(nums[i]);backtracking(pos 1,map, nums, path, res);path.pop_back();map[i] false;}}}vectorvectorint permuteUnique(vectorint nums) {unordered_mapint, bool map;vectorvectorint res;vectorint path;unordered_mapint, bool used;backtracking(0,map, nums, path, res);return res;}
};
class Solution {
public:void backtracking(int pos,unordered_mapint, bool map, vectorint nums, vectorint path, vectorvectorint res) {if (path.size() nums.size()){res.emplace_back(path);return;}bool used[21] { false };for (int i 0;i nums.size();i) {if (! used[nums[i]10] !map[i]) {used[nums[i] 10] true;map[i] true;path.push_back(nums[i]);backtracking(pos 1,map, nums, path, res);path.pop_back();map[i] false;}}}vectorvectorint permuteUnique(vectorint nums) {unordered_mapint, bool map;vectorvectorint res;vectorint path;unordered_mapint, bool used;backtracking(0,map, nums, path, res);return res;}
};
五、棋盘问题 N 皇后 class Solution {
public:bool isok(int x, int y, int n, vectorstring path) {// 同一列不同行检查for (int i 0;i x;i) {if (path[i][y] Q) {return false;}}// 右上对角线检查for (int i x, j y;i 0 j n;i--, j) {if (path[i][j] Q) {return false;}}// 左上对角线检查for (int i x, j y;i 0 j 0;i--, j--) {if (path[i][j] Q) {return false;}}return true;}void backtracking(int pos,int n, vectorstring path, vectorvectorstring res) {if (pos n) {res.push_back(path);return;}for (int i 0;i n;i) {if (isok( pos, i, n, path)) {path[pos][i] Q;backtracking(pos 1, n, path, res);path[pos][i] .;}}}vectorvectorstring solveNQueens(int n) {vectorvectorstring res;vectorstring path(n, string(n, .));backtracking(0, n, path, res);return res;}
};
