一、概念
參考文章
回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。
許多復(fù)雜的，規(guī)模較大的問(wèn)題都可以使用回溯法，有“通用解題方法”的美稱。
二、基本思想
在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法）。
若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。
而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。
三、用回溯法解題的一般步驟：
- 針對(duì)所給問(wèn)題，確定問(wèn)題的解空間：首先應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間應(yīng)至少包含問(wèn)題的一個(gè)（最優(yōu)）解。
- 確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則
- 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。
四、算法模板
/**
* dfs模板.
* @param[in] input 輸入數(shù)據(jù)指針
* @param[out] path 當(dāng)前路徑，即中間結(jié)果
* @param[out] result 最終結(jié)果
* @param[inout] cur or gap 標(biāo)記當(dāng)前位置或距離目標(biāo)的距離
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
if (數(shù)據(jù)非法) return 0; // 終止條件
if (滿足條件) {
將path 放入result
}
if (可以剪枝) return;
for(...) { // 執(zhí)行所有可能的擴(kuò)展動(dòng)作
執(zhí)行動(dòng)作，修改path
dfs(input, path, result, cur + 1 or gap--, );
恢復(fù)path //向前回溯
}
}
五、檢測(cè)一下是不是真的會(huì)了呢
1.leetcode401-二進(jìn)制手表
題目描述
二進(jìn)制手表頂部有 4 個(gè) LED 代表小時(shí)（0-11），底部的 6 個(gè) LED 代表分鐘（0-59）。每個(gè) LED 代表一個(gè) 0 或 1，最低位在右側(cè)。
例如，上面的二進(jìn)制手表讀取 “3:25”。給定一個(gè)非負(fù)整數(shù) n 代表當(dāng)前 LED 亮著的數(shù)量，返回所有可能的時(shí)間。
輸入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
回溯法
這個(gè)題目可以歸于有多少 n個(gè)1的二進(jìn)制組合。轉(zhuǎn)換為字符串即可。 這里將 0 - 9，劃分一下 0 - 3 是 小時(shí)， 6 - 9 是分鐘計(jì)算。
- 結(jié)束條件: num==0且h,m合法
- 退出條件: h或m非法
class Solution {
public:
void readBinaryWatch(vector<string> &res, int h, int m, int num, int cur){
if(num==0 && h>=0 && m>=0){
string s = to_string(h) + (m<10 ? ":0" : ":") + to_string(m);
res.push_back(s);
}
for(int i=cur;i<10;i++){
if(i<=3){
h += pow(2, i);
if(h>11){
h -= pow(2, i);
continue;
}
}else{
m += pow(2, i-4);
if(m>59) return;
}
readBinaryWatch(res, h, m, num-1, i+1);
if(i<=3) h -= pow(2, i);
else m -= pow(2, i-4);
}
}
vector<string> readBinaryWatch(int num) {
vector<string> res;
if(num<0 || num>8) return res;
readBinaryWatch(res, 0, 0, num, 0);
return res;
}
};
bitset法
class Solution {
public:
vector<string> readBinaryWatch(int num) {//bitset STL模板
vector<string> times;
for (int i = 0; i < 12; i++) {
bitset<4> h(i);//4位的二進(jìn)制數(shù)
for (int j = 0; j < 60; j++) {
bitset<6> m(j);//6位的二進(jìn)制數(shù)
if (h.count() + m.count() == num)//h.count()函數(shù)判斷h中1的個(gè)數(shù)
times.push_back(to_string(i) + (j < 10? ":0": ":") + to_string(j));
}
}
return times;
}
};
2.leetcode39-組合總數(shù)
題目描述
給定一個(gè)無(wú)重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的數(shù)字可以無(wú)限制重復(fù)被選取。
說(shuō)明：
所有數(shù)字（包括 target）都是正整數(shù)。解集不能包含重復(fù)的組合。
示例 :
輸入: candidates = [2,3,6,7], target = 7,所求解集為:
[[7],
[2,2,3]]
回溯法
解空間是任意選取的任意個(gè)數(shù)字組成的數(shù)組.遍歷數(shù)組中的值，如果nums[i] < target , 嘗試把nums[i]作為一個(gè)加數(shù)，把目標(biāo)值減去nums[i]，下一次遞歸從i+1開(kāi)始遍歷數(shù)組尋找下一個(gè)加數(shù);如果target=0，說(shuō)明找到了一組加數(shù);否則把上一個(gè)加數(shù)從list中去掉.
- 結(jié)束條件: target==0
- 退出條件: target<0
class Solution {
public:
void dfs(vector<vector<int>> &res, vector<int> &temp, vector<int> candidates, int target, int index){
if(target<0) return ;
if(target==0){
res.push_back(temp);
}
for(int i=index; i < candidates.size(); i++){
target -= candidates[i];
temp.push_back(candidates[i]);
dfs(res, temp, candidates, target, i);
target += candidates[i];
temp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> temp;
dfs(res, temp, candidates, target, 0);
return res;
}
};
3.leetcode40-組合總數(shù) II
題目描述
給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
說(shuō)明：所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。解集不能包含重復(fù)的組合。
示例:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集為:
[[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]]
回溯法
和上一題基本相同,唯一需要注意的是每個(gè)數(shù)字只許使用一次且不能有重復(fù)組合.
可先對(duì)數(shù)組排序,保留深度方向上相同的數(shù)字（也就是多個(gè)重復(fù)數(shù)字時(shí)可用，比如[1,1,1],第一個(gè)‘1’使用過(guò)后，第二和第三個(gè)依然可以使用），剔除水平方向相同的（也就是同一層中相同的枝應(yīng)該剪掉）。
- 結(jié)束條件: target==0
- 退出條件: target<0
代碼
class Solution {
public:
void dfs(vector<vector<int>> &res, vector<int> &temp, vector<int> candidates, int target, int index){
if(target<0) return;
if(target==0){
res.push_back(temp);
}
for(int i=index; i<candidates.size()&&candidates[i]<=target;i++){
if(i>index&&candidates[i-1]==candidates[i]) continue;
target -= candidates[i];
temp.push_back(candidates[i]);
dfs(res, temp, candidates, target, i+1);
target += candidates[i];
temp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> temp;
if(candidates.size()==0) return res;
sort(candidates.begin(), candidates.end());
dfs(res, temp, candidates, target, 0);
return res;
}
};
4.leetcode46-全排列
題目描述
給定一個(gè)沒(méi)有重復(fù)數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]]
回溯法
- 對(duì)現(xiàn)有序列 x 進(jìn)行遍歷，拿到每一個(gè)遍歷值放在當(dāng)前位上
- 將該遍歷到的值抽離序列 x，生成一個(gè)新的序列 y
- 繼續(xù)對(duì)序列 y 執(zhí)行這一過(guò)程
代碼
class Solution {
public:
void dfs(vector<vector<int>> &res, vector<int> &nums, int left, int right){
if(left==right){
res.push_back(nums);
}
for(int i=left;i<=right;i++){
swap(nums[i], nums[left]);
dfs(res, nums, left+1, right);
swap(nums[i], nums[left]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
dfs(res, nums, 0, nums.size()-1);
return res;
}
};
5.leetcode47-全排列II
題目描述
給定一個(gè)可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。
示例:
輸入: [1,1,2]
輸出:
[[1,1,2],
[1,2,1],
[2,1,1]]
回溯法
代碼一
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
permute(nums, 0, res);
return res;
}
void permute(vector<int> nums, int start, vector<vector<int>>& res) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); ++i) {
if (i != start && nums[i] == nums[start]) continue;
swap(nums[i], nums[start]);
permute(nums, start + 1, res);
}
}
};
代碼二
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
for (int v : nums) um[v]++;
vector<int> perm;
helper(perm, nums.size());
return ret;
}
void helper(vector<int> &perm, int num) {
if (perm.size() == num) {
ret.push_back(perm);
return;
}
for (auto &it : um) {
if (it.second > 0) {
it.second--;
perm.push_back(it.first);
helper(perm, num);
perm.pop_back();
it.second++;
}
}
}
private:
unordered_map<int, int> um;
vector<vector<int>> ret;
};
6.leetcode78-子集
題目描述
給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說(shuō)明：解集不能包含重復(fù)的子集。
示例:
輸入: nums = [1,2,3]
輸出:
[ [3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]]
回溯法
添加一個(gè)數(shù)，遞歸，刪除之前的數(shù)，下次循環(huán)。
代碼
class Solution {
public:
void dfs(vector<vector<int>> &res, vector<int> &temp, vector<int> nums, int index){
res.push_back(temp);
for(int i=index; i<nums.size();i++){
temp.push_back(nums[i]);
dfs(res, temp, nums, i+1);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
dfs(res, temp, nums, 0);
return res;
}
};
7.leetcode51-N皇后
題目描述
n 皇后問(wèn)題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
上圖為 8 皇后問(wèn)題的一種解法。給定一個(gè)整數(shù) n，返回所有不同的 n 皇后問(wèn)題的解決方案。每一種解法包含一個(gè)明確的 n 皇后問(wèn)題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。
示例:
輸入: 4
輸出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]]
解釋: 4 皇后問(wèn)題存在兩個(gè)不同的解法。
回溯法
用set記錄 列, 正對(duì)角,負(fù)對(duì)角是否已經(jīng)擺放過(guò)皇后，如果是則跳過(guò)啊！
如何判斷是否在對(duì)角上呢?
- 正對(duì)角就是相加之和一樣的
- 負(fù)對(duì)角就是相減只差一樣的
代碼
class Solution {
public:
void dfs(int row, vector<vector<string>> &res, vector<string> &temp,
unordered_set<int> &cols, unordered_set<int> &hills, unordered_set<int> dales, int n){
if(row==n){
res.push_back(temp);
return ;
}
for(int col=0;col<n;col++){
if(cols.count(col)>0 || hills.count(col+row)>0 || dales.count(row-col)>0) continue;
cols.insert(col);
hills.insert(col+row);
dales.insert(row-col);
temp[row][col] = 'Q';
dfs(row+1, res, temp, cols, hills, dales, n);
cols.erase(col);
hills.erase(col+row);
dales.erase(row-col);
temp[row][col] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> temp(n, string(n, '.'));
unordered_set<int> cols;
unordered_set<int> hills;
unordered_set<int> dales;
dfs(0, res, temp, cols, hills, dales, n);
return res;
}
};
8.leetcode52-N皇后II
題目描述
n 皇后問(wèn)題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
上圖為 8 皇后問(wèn)題的一種解法。給定一個(gè)整數(shù) n，返回 n 皇后不同的解決方案的數(shù)量。
示例:
輸入: 4
輸出: 2
解釋: 4 皇后問(wèn)題存在如下兩個(gè)不同的解法。
[[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]]
回溯法
和上一題一樣，這里如果滿足情況加1即可，比上題簡(jiǎn)單一些！
代碼
class Solution {
public:
void dfs(unordered_set<int> &cols, unordered_set<int> &hills, unordered_set<int> &dales, int &res, int row, int n){
if(row==n){
res++;
return ;
}
for(int i=0;i<n;i++){
if(cols.count(i)>0 || hills.count(i+row)>0 || dales.count(row-i)>0) continue;
cols.insert(i);
hills.insert(i+row);
dales.insert(row-i);
dfs(cols, hills, dales, res, row+1, n);
cols.erase(i);
hills.erase(i+row);
dales.erase(row-i);
}
}
int totalNQueens(int n) {
unordered_set<int> cols;
unordered_set<int> hills;
unordered_set<int> dales;
int res=0;
dfs(cols, hills, dales, res, 0, n);
return res;
}
};