回溯算法（C/C++）

目录

 一、组合问题

组合

组合剪枝

组合总和 III​编辑

组合总和​编辑

组合总和 II

电话号码的字母组合​编辑

二、分割问题

分割回文串

复原 IP 地址

三、集合问题

子集

子集 II

 非递减子序列

四、排列问题

全排列

全排列 II

五、棋盘问题

 N 皇后

---

课程：

【带你学透回溯算法（理论篇）| 回溯法精讲！】https://www.bilibili.com/video/BV1cy4y167mM?vd_source=342079de7c07f82982956aad8662b467

关于回溯算法，你该了解这些！

• 组合问题：N个数里面按一定规则找出k个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

 一、组合问题

组合

class Solution {
public:void backtracking(int pos, vector<int> &path, vector<vector<int>>& res, int k, int n) {if (path.size()==k) {res.push_back(path);return;}for (int i = pos;i < n+1;i++) {path.push_back(i);backtracking(i + 1, path, res, k, n);path.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> 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, vector<int> &path, vector<vector<int>>& 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();}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> path;backtracking(1, path, res, k, n);return res;}
};

下面三个案例练练手看看。

组合总和 III

class Solution {
public:void backtracking(int pos,int &sum,int n, int k,vector<int> &path ,vector<vector<int>> &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();}}}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> re;vector<int> path;int sum = 0;backtracking(1, sum, n, k, path, re);return re;}
};

这里可以看到执行的剪枝操作就是，当sum+i大于目标值n的时候就不执行深度递归操作。

组合总和

class Solution {
public:void backtracking(int pos, int sum, int target, vector<vector<int>>& re, vector<int>& candidates,vector<int> path) {if (sum == target) {re.push_back(path);return;}if(pos==candidates.size() || sum>target){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();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());vector<vector<int>> re;vector<int> path;backtracking(0, 0, target, re, candidates, path);return re;}
};

组合总和 II

class Solution {
public:void backtracking(int pos,int target, int sum,unordered_map<int, bool> used ,vector<int> path, vector<int> candidates,vector<vector<int>> &re){if (sum == target) {re.push_back(path);return;}for (int i = pos;i < candidates.size() && sum + candidates[i] <= target;i++) {if(i>0 && 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;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<vector<int>> re;vector<int> path;unordered_map<int, bool> used;backtracking(0, target, 0, used, path, candidates, re);return re;}
};

电话号码的字母组合

class Solution {
public:void backtracking(int pos,string path,string digits, vector<string> map, vector<string>& 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();}}vector<string> letterCombinations(string digits) {vector<string> map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> 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, vector<string> route, string path, string s, vector<vector<string>> &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-pos+1);if (is_huiwen(temp)) {route.push_back(temp);backtracking(i + 1, route, path, s, res);route.pop_back();}}}vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> 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 || num<0) {return false;}return true;}void backtracking(int pos,int start, string tmp, string s, vector<string>& 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-start+1);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--;}}}vector<string> restoreIpAddresses(string s) {vector<string> res;string tmp;backtracking(0,0, tmp, s, res);return res;}
};

三、集合问题

 对于子集问题，其实跟前面的不同，子集是每一个递归的节点都要进行数据的收集，而前面的组合问题都是有条件限制的才执行收集的操作，比如递归收集数字和为target的组合之类的。

子集

回溯算法：求子集问题！

class Solution {
public:void backtracking(int start_index, vector<int>& nums, vector<int>& path, vector<vector<int>>& 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();}}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(0, nums, path, res);return res;}
};

子集 II

这个问题其实是组合总和2的一个派生问题，本质上是差不多的，无法就是需要一个东西来去标记一下使用过的数据，避免下次重新去使用。

class Solution {
public:void backtracking(int pos, unordered_map<int, bool> &used, vector<int>& nums, vector<int>& path, vector<vector<int>>& 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();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res;vector<int> path;unordered_map<int, bool> used;backtracking(0, used, nums, path, res);return res;}
};

 非递减子序列

对于这个问题，也就是说每一层需要去避免重复使用同一个数字，也就是需要在每一个递归节点去创建一个作为标记的哈希表来依次标记已经遍历的节点，这里对比前面使用了纵向哈希表是不一样的，这个是横向的。

class Solution {
public:void backtracking(int pos,vector<int> &path, vector<int>& nums,vector<vector<int>> &res) {if(path.size()>=2)res.emplace_back(path);if (pos == nums.size()) {return;}unordered_map<int, 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();}}vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(0, path, nums, res);return res;}
};

class Solution {
public:void backtracking(int pos,vector<int> &path, vector<int>& nums,vector<vector<int>> &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();}}vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(0, path, nums, res);return res;}
};

四、排列问题

全排列

class Solution {
public:void backtracking(int pos,unordered_map<int, bool>& used, vector<int>& nums, vector<int>& path, vector<vector<int>>& 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();}}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> path;unordered_map<int, bool> used;backtracking(0,used, nums, path, res);return res;}
};

全排列 II

class Solution {
public:void backtracking(int pos,unordered_map<int, bool> &map, vector<int> &nums, vector<int> &path, vector<vector<int>>& 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;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {unordered_map<int, bool> map;vector<vector<int>> res;vector<int> path;unordered_map<int, bool> used;backtracking(0,map, nums, path, res);return res;}
};

class Solution {
public:void backtracking(int pos,unordered_map<int, bool> &map, vector<int> &nums, vector<int> &path, vector<vector<int>>& 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;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {unordered_map<int, bool> map;vector<vector<int>> res;vector<int> path;unordered_map<int, bool> used;backtracking(0,map, nums, path, res);return res;}
};

五、棋盘问题

 N 皇后

class Solution {
public:bool isok(int x, int y, int n, vector<string>& 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, vector<string>& path, vector<vector<string>>& 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] = '.';}}}vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<string> path(n, string(n, '.'));backtracking(0, n, path, res);return res;}
};