文章目錄
- 前言
- 遞回
- N叉樹的遍歷
- 節點設計
- N叉樹的前序遍歷
- 后序遍歷
- 層序遍歷
- 回溯例題精講
- 島嶼最大面積
- 思路
- 代碼實作
- 八皇后問題
- 思路
- 代碼實作
- 括號生成
- 思路
- 代碼實作
- 全排列
- 思路
- 代碼實作
- 再說兩句
- 解回溯題的一般步驟
- 電話號碼的字母組合
- 思路
- 代碼實作
- 子集
- 思路
- 代碼實作
前言
回溯演算法，之前也是寫過的，感徑訓不錯，但是之前分成兩篇寫了，現在重新整理一下，順便我自己也回顧一下，
遞回
要玩得轉回溯演算法，遞回思想就要融入骨子里，
正好早上我整理了一篇遞回相關的，不妨看一下：【C++】演算法集錦（2）：遞回
N叉樹的遍歷
我們從N叉樹的遍歷入手，來看一下回溯演算法，
思考一下二叉樹的回顧一下二叉樹的遍歷方式：
前序遍歷 - 首先訪問根節點，然后遍歷左子樹，最后遍歷右子樹；
中序遍歷 - 首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹；
后序遍歷 - 首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點；
層序遍歷 - 按照從左到右的順序，逐層遍歷各個節點，
N 叉樹的中序遍歷沒有標準定義，中序遍歷只有在二叉樹中有明確的定義，
我們跳過 N 叉樹中序遍歷的部分，
節點設計
class Node {
public:
int val;
vector<Node*> children; //注意，這里不再是左右子節點了
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
N叉樹的前序遍歷
給定一個 N 叉樹，回傳其節點值的前序遍歷，
class Solution {
public:
void preorderDFS(Node* root, int index, vector<int>& ret) {
if (root == NULL)
return;
ret.push_back(root->val);
int sz = (root->children).size();
while (index < sz) {
preorderDFS(root->children[index], 0, ret); //認真捋一下這一步
index += 1;
}
}
vector<int> preorder(Node* root) {
vector<int> ret;
preorderDFS(root, 0, ret);
return ret;
}
};
后序遍歷
給定一個 N 叉樹，回傳其節點值的后序遍歷，
class Solution {
public:
void postorderDFS(Node* root, int index, vector<int>& ret) {
if (root == NULL)
return;
int sz = (root->children).size();
while (index < sz) {
postorderDFS(root->children[index], 0, ret);
index += 1;
}
ret.push_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> ret;
postorderDFS(root, 0, ret);
return ret;
}
};
層序遍歷
給定一個 N 叉樹，回傳其節點值的層序遍歷， (即從左到右，逐層遍歷)，
class Solution {
public:
vector<vector<int>> result;
void dfs(Node* root, int dep){
if(!root) return;
if(dep == result.size()) result.emplace_back();
result[dep].push_back(root->val);
auto children = root->children;
for(auto ele:children){
dfs(ele, dep+1);
}
}
vector<vector<int>> levelOrder(Node* root) {
dfs(root, 0);
return result;
}
};
島嶼最大面積、八皇后問題、括號生成感覺比較簡單，所以思路講的就比較簡陋，適合入門練手，建議看其他題目的講解（全排列那題），
回溯例題精講
島嶼最大面積
給定一個包含了一些 0 和 1 的非空二維陣列 grid ，
一個 島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直方向上相鄰，你可以假設 grid 的四個邊緣都被 0（代表水）包圍著，
找到給定的二維陣列中最大的島嶼面積，(如果沒有島嶼，則回傳面積為 0 ，)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
對于上面這個給定矩陣應回傳 6，注意答案不應該是 11 ，因為島嶼只能包含水平或垂直的四個方向的 1 ，
示例 2:
[[0,0,0,0,0,0,0,0]]
對于上面這個給定的矩陣, 回傳 0，
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/max-area-of-island
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
思路
這題其實我自己做出來了，把它放在第一題嘛，我覺得因為它是比較簡單的，
從頭開始遍歷，遇到“1”就展開上下左右搜索，搜空了就回溯，在搜索程序中計數，并將搜索到的位置全部置0，防止二次污染，
代碼實作
int checkIsland(vector<vector<int>>& grid, int x, int y) {
int count = 0;
if (grid[x][y] == 0)
return count;
else {
grid[x][y] = 0;
count++;
//上
if (x - 1 >= 0)
count += checkIsland(grid, x - 1, y);
//右
if ((y + 1) < grid[0].size())
count += checkIsland(grid, x, y + 1);
//下
if ((x + 1) < grid.size())
count += checkIsland(grid, x + 1, y);
//左
if ((y - 1) >= 0)
count += checkIsland(grid, x, y - 1);
}
return count;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.size() == 0)
return 0;
int max = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
int temp = checkIsland(grid, i, j);
if (temp > max)
max = temp;
}
}
}
return max;
}
八皇后問題
八皇后問題是一個古老的問題，于1848年由一位國際象棋棋手提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，如何求解？
思路
將每一個棋子放在當前列的最前端，再放下一個棋子，
如果下一個棋子沒地方放了，就回溯到前一個棋子，將其往后一個適宜位置挪動，
具體思路都在代碼里了，
代碼實作
#include<iostream>
using namespace std;
#define MAX_NUM 8 //皇后數量
int queen[MAX_NUM][MAX_NUM] = { 0 };
bool check(int x, int y) { //檢查一個坐標是否可以放置
for (int i = 0; i < y; i++) {
if (queen[x][i] == 1) { //這一行是否可以存在
return false;
}
if (x - 1 - i > 0 && queen[x - 1 - i][y - 1 - i] == 1) { //檢查左斜列
return false;
}
if (x + 1 + i < MAX_NUM && queen[x + 1 + i][y + 1 + i] == 1) { //檢查右斜列
return false;
}
}
queen[x][y] = 1;
return true;
}
void showQueen() {
for (int i = 0; i < MAX_NUM; i++) {
for (int j = 0; j < MAX_NUM; j++) {
cout << queen[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
bool settleQueen(int x) {
if (x == MAX_NUM) { //遍歷完畢，找到答案
return true;
}
for (int i = 0; i < MAX_NUM; i++) {
for (int y = 0; y < MAX_NUM; y++) {
queen[y][x] = 0; //清空當前列，省的回溯的時候被打擾
}
if (check(i,x)) { //如果這行找著了
queen[i][x] = 1;
showQueen(); //直觀測驗結果
if (settleQueen(x + 1)) { //是時候往左了
return true; //一路往左
}
}
}
return false; //如果不行，就退回來
}
括號生成
數字 n 代表生成括號的對數，請你設計一個函式，用于能夠生成所有可能的并且 有效的 括號組合，
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/generate-parentheses
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
思路
如果左括號數量不大于 n，我們可以放一個左括號，如果右括號數量小于左括號的數量，我們可以放一個右括號，
代碼實作
vector<string> generateParenthesis(int n) {
vector<string> res;
generateParenthesisDFS(n, n, "", res);
return res;
}
void generateParenthesisDFS(int left, int right, string out, vector<string> &res) {
if (left > right) return;
if (left == 0 && right == 0) res.push_back(out);
else {
if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res);
if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res);
}
}
全排列
給定一個 沒有重復 數字的序列，回傳其所有可能的全排列，
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/permutations
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
怎么用，是不是感覺千頭萬緒，但是又捋不出一個頭緒來，很難受，
思路
“全排列”就是一個非常經典的“回溯”演算法的應用，我們知道，N 個數字的全排列一共有 N! 這么多個，
大家可以嘗試一下在紙上寫 3 個數字、4 個數字、5 個數字的全排列，相信不難找到這樣的方法，
以陣列 [1, 2, 3] 的全排列為例，
我們先寫以 1 開頭的全排列，它們是：[1, 2, 3], [1, 3, 2]；
再寫以 2 開頭的全排列，它們是：[2, 1, 3], [2, 3, 1]；
最后寫以 3 開頭的全排列，它們是：[3, 1, 2], [3, 2, 1]，
我們只需要按順序列舉每一位可能出現的情況，已經選擇的數字在接下來要確定的數字中不能出現，按照這種策略選取就能夠做到不重不漏，把可能的全排列都列舉出來，
在列舉第一位的時候，有 3 種情況，
在列舉第二位的時候，前面已經出現過的數字就不能再被選取了；
在列舉第三位的時候，前面 2 個已經選擇過的數字就不能再被選取了，
使用編程的方法得到全排列，就是在這樣的一個樹形結構中進行編程，具體來說，就是執行一次深度優先遍歷，從樹的根結點到葉子結點形成的路徑就是一個全排列，
說明：
1、每一個結點表示了“全排列”問題求解的不同階段，這些階段通過變數的“不同的值”體現；
2、這些變數的不同的值，也稱之為“狀態”；
3、使用深度優先遍歷有“回頭”的程序，在“回頭”以后，狀態變數需要設定成為和先前一樣；
4、因此在回到上一層結點的程序中，需要撤銷上一次選擇，這個操作也稱之為“狀態重置”；
5、深度優先遍歷，可以直接借助系統堆疊空間，為我們保存所需要的狀態變數，在編碼中只需要注意遍歷到相應的結點的時候，狀態變數的值是正確的，具體的做法是：往下走一層的時候，path 變數在尾部追加，而往回走的時候，需要撤銷上一次的選擇，也是在尾部操作，因此 path 變數是一個堆疊，
6、深度優先遍歷通過“回溯”操作，實作了全域使用一份狀態變數的效果，
下面我們解釋如何編碼：
1、首先這棵樹除了根結點和葉子結點以外，每一個結點做的事情其實是一樣的，即在已經選了一些數的前提，我們需要在剩下還沒有選擇的數中按照順序依次選擇一個數，這顯然是一個遞回結構；
2、遞回的終止條件是，數已經選夠了，因此我們需要一個變數來表示當前遞回到第幾層，我們把這個變數叫做 depth；
3、這些結點實際上表示了搜索（查找）全排列問題的不同階段，為了區分這些不同階段，我們就需要一些變數來記錄為了得到一個全排列，程式進行到哪一步了，在這里我們需要兩個變數：
（1）已經選了哪些數，到葉子結點時候，這些已經選擇的數就構成了一個全排列；
（2）一個布爾陣列 used，初始化的時候都為 false 表示這些數還沒有被選擇，當我們選定一個數的時候，就將這個陣列的相應位置設定為 true ，這樣在考慮下一個位置的時候，就能夠以 O(1) 的時間復雜度判斷這個數是否被選擇過，這是一種“以空間換時間”的思想，
我們把這兩個變數稱之為“狀態變數”，它們表示了我們在求解一個問題的時候所處的階段，
4、在非葉子結點處，產生不同的分支，這一操作的語意是：在還未選擇的數中依次選擇一個元素作為下一個位置的元素，這顯然得通過一個回圈實作，
5、另外，因為是執行深度優先遍歷，從較深層的結點回傳到較淺層結點的時候，需要做“狀態重置”，即“回到過去”、“恢復現場”，我們舉一個例子，
從 [1, 2, 3] 到 [1, 3, 2] ，深度優先遍歷是這樣做的，從 [1, 2, 3] 回到 [1, 2] 的時候，需要撤銷剛剛已經選擇的數 3，因為在這一層只有一個數 3 我們已經嘗試過了，因此程式回到上一層，需要撤銷對 2 的選擇，好讓后面的程式知道，選擇 3 了以后還能夠選擇 2，
這種在遍歷的程序中，從深層結點回到淺層結點的程序中所做的操作就叫“回溯”，
作者：liweiwei1419
鏈接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
來源：力扣（LeetCode） 著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
代碼實作
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty()) return {};
// 存放最后結果
vector<vector<int>> ans;
// 存放某一個排列
vector<int> temp;
// 判斷該數字是否被使用過
vector<bool> used(nums.size(),false);
// 進行遞回求解
dfs(ans,temp,used,nums);
return ans;
}
void dfs(vector<vector<int>>& ans,vector<int>& temp,vector<bool>& used,
const vector<int>& nums)
{
// 如果當前排列陣列的長度等于輸入陣列的長度
// 該排列已完成
// 將該排列的加入結果中，回傳
if(temp.size()==nums.size())
{
ans.push_back(temp);
return;
}
// 回圈的進行列舉所有狀態
for(int i=0;i<nums.size();++i)
{
// 該數字已經選擇過，跳過
if(used.at(i)) continue;
// 選擇當前數字
temp.push_back(nums.at(i));
// 記錄該數字已被選擇
used.at(i)=true;
// 遞回選擇下一個數字
dfs(ans,temp,used,nums);
// 回溯，撤銷當前選擇
used.at(i)=false;
temp.pop_back();
}
}
再說兩句
1、為什么使用深度優先遍歷？
（1）首先是正確性，只有遍歷狀態空間，才能得到所有符合條件的解；
（2）在深度優先遍歷的時候，不同狀態之間的切換很容易，可以再看一下上面有很多箭頭的那張圖，每兩個狀態之間的差別只有 1 處，因此回退非常方便，這樣全域才能使用一份狀態變數完成搜索；
（3）如果使用廣度優先遍歷，從淺層轉到深層，狀態的變化就很大，此時我們不得不在每一個狀態都新建變數去保存它，從性能來說是不劃算的；
（4）如果使用廣度優先遍歷就得使用佇列，然后撰寫結點類，使用深度優先遍歷，我們是直接使用了系統堆疊，系統堆疊幫助我們保存了每一個結點的狀態資訊，于是我們不用撰寫結點類，不必手動撰寫堆疊完成深度優先遍歷，大家可以嘗試使用廣度優先遍歷實作一下，就能體會到這一點，
2、不回溯可不可以？
可以，搜索問題的狀態空間一般很大，如果每一個狀態都去創建新的變數，時間復雜度是 O(N)，在候選數比較多的時候，在非葉子結點上創建新的狀態變數的性能消耗就很嚴重，
就本題而言，只需要葉子結點的那個狀態，在葉子結點執行拷貝，時間復雜度是 O(N)，路徑變數在深度優先遍歷的時候，結點之間的轉換只需要 O(1)，
最后，由于回溯演算法的時間復雜度很高，因此，如果在遍歷的時候，如果能夠提前知道這一條分支不能搜索到滿意的結果，就可以提前結束，這一步操作稱之為剪枝，
回溯演算法會大量應用“剪枝”技巧達到以加快搜索速度，有些時候，需要做一些預處理作業（例如排序）才能達到剪枝的目的，預處理作業雖然也消耗時間，但一般而且能夠剪枝節約的時間更多，還有正是因為回溯問題本身時間復雜度就很高，所以能用空間換時間就盡量使用空間，否則時間消耗又上去了，
作者：liweiwei1419
鏈接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
來源：力扣（LeetCode） 著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
解回溯題的一般步驟
第 1 步都是先畫圖，畫圖是非常重要的，只有畫圖才能幫助我們想清楚遞回結構，想清楚如何剪枝，就拿題目中的示例，想一想人手動操作是怎么做的，一般這樣下來，這棵遞回樹都不難畫出，
即在畫圖的程序中思考清楚：
1、分支如何產生；
2、題目需要的解在哪里？是在葉子結點、還是在非葉子結點、還是在從跟結點到葉子結點的路徑？
3、哪些搜索是會產生不需要的解的？例如：產生重復是什么原因，如果在淺層就知道這個分支不能產生需要的結果，應該提前剪枝，剪枝的條件是什么，代碼怎么寫？
作者：liweiwei1419
鏈接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
來源：力扣（LeetCode） 著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
電話號碼的字母組合
給定一個僅包含數字 2-9 的字串，回傳所有它能表示的字母組合，
給出數字到字母的映射如下（與電話按鍵相同），注意 1 不對應任何字母，
示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
思路
在前面的一些步驟做出一些修改，并重新嘗試找到可行解，
給出如下回溯函式 backtrack(combination, next_digits) ，它將一個目前已經產生的組合 combination 和接下來準備要輸入的數字 next_digits 作為引數，
如果沒有更多的數字需要被輸入，那意味著當前的組合已經產生好了，
如果還有數字需要被輸入：
遍歷下一個數字所對應的所有映射的字母，
將當前的字母添加到組合最后，也就是 combination = combination + letter ，
重復這個程序，輸入剩下的數字： backtrack(combination + letter, next_digits[1:]) ，
代碼實作
其實代碼里的備注還更加全全面
//1. 用map記錄每個數字按鍵對應的所有字母
map<char, string> M = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
{'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
//2. 存盤最終結果和臨時結果的變數
vector<string> ans;
string current;
//3. DFS函式，index是生成臨時結果字串的下標，
//每一個digits[index]數字對應臨時結果current[index]的一位字母
void DFS(int index, string digits) {
//出口
if(index == digits.size()) {
ans.push_back(current);
return;
}
//遞回呼叫
//對于當前輸入的第index號數字(digits[index])，
//列舉其對應的所有字母(M[digits[index]][i])
for(int i = 0; i < M[digits[index]].size(); i++) {
current.push_back(M[digits[index]][i]); //臨時結果壓入一個字母
DFS(index + 1, digits); //以在當前位置壓入該字母這一“情況”為前提，構造此“分支”的后續結果
current.pop_back(); //狀態還原，例如臨時結果從 "ab" -> "a"，下一次回圈嘗試"ac"
}
}
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) {
return ans;
}
DFS(0, digits);
return ans;
}
子集
給定一組不含重復元素的整數陣列 nums，回傳該陣列所有可能的子集（冪集），
說明：解集不能包含重復的子集，
示例:
輸入: nums = [1,2,3]
輸出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/subsets
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
思路
定義一個回溯方法 backtrack(first, curr)，第一個引數為索引 first，第二個引數為當前子集 curr，
如果當前子集構造完成，將它添加到輸出集合中，
否則，從 first 到 n 遍歷索引 i，
將整數 nums[i] 添加到當前子集 curr，
繼續向子集中添加整數：backtrack(i + 1, curr)，
從 curr 中洗掉 nums[i] 進行回溯，
代碼實作
class Solution {
private:
vector<vector<int>> ret;
vector<int> temp;
public:
void DFS(vector<int>& nums,int pre,int level) {
//退出條件：前面插入的是陣列中最后一個元素
if (pre == nums.back()) {
temp.clear();
return;
}
for (int i = 0; i < nums.size(); i++) {
if (nums[i] <= pre)
continue;
temp.push_back(nums[i]);
ret.push_back(temp);
DFS(nums, nums[i],i+1);
if (level)
return;
}
}
vector<vector<int>> subsets(vector<int>& nums) {
ret.push_back({});
if (nums.empty())
return ret;
DFS(nums, INT_MIN,0);
return ret;
}
};
到這兒到這兒，燒腦啊，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261327.html
標籤：AI
上一篇：【C++入門】C++ STL概述