文章目錄

• 回溯
• • 電話號碼的字母組合
  • • 二進制手表
  • 組合總數
  • 全排列
  • • 活字印刷
  • N皇后
  • • N皇后II

---

回溯

回溯是一種通過窮舉所有可能情況來找到所有解的算法。如果一個候選解最后被發現并不是可行解，回溯算法會舍棄它，并在前面的一些步驟做出一些修改，并重新嘗試找到可行解。

當探索到某一步時，發現原先選擇并不優或 達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。也可以稱為剪枝點，所謂的剪枝，指的是把不會找到目標，或者不必要的路徑裁剪掉。

從上面看出，回溯其實就是選優搜索法，按照深度優先搜索的方式進行搜索，再通過剪枝來避免不相關結果。

//模板 回溯() {if(滿足結束條件){將結果加入結果集中return;}for(當前選擇 : 選擇列表){1.完成這一步的選擇2.回溯(下一步), 進行下一步的選擇3.撤銷選擇，繼續進行其他嘗試} }

---

電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

DFS + 回溯，如果當前組合行不通則回溯到上一步，然后繼續嘗試其他組合。

class Solution { public:vector<string> numToStr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //數字——字母映射void DFS(vector<string>& res, string& digits, string cur, int index){//此時數字已遍歷結束if(index == digits.size()){//如果組合不為空，則加入結果集中if(!cur.empty()){res.push_back(cur);return;}}//搜索當前所有可能的組合for(auto ch : numToStr[digits[index] - '0']){cur.push_back(ch);DFS(res, digits, cur, index + 1);//回溯到上一步的狀態cur.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.empty()){return {};}vector<string> res;DFS(res, digits, "", 0);return res;} };

二進制手表

二進制手表頂部有 4 個 LED 代表 小時（0-11），底部的 6 個 LED 代表 分鐘（0-59）。

每個 LED 代表一個 0 或 1，最低位在右側。

例如，上面的二進制手表讀取 “3:25”。

給定一個非負整數 n 代表當前 LED 亮著的數量，返回所有可能的時間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-watch

和上題思路一樣，不過變為了組合二進制。

class Solution { public:vector<int> nToTime = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};void DFS(vector<string>& res, int num, int index, pair<int, int>& time){//如果沒有剩余的燈，就返回if(num == 0){if(time.first > 11 || time.second > 59){return;}string cur = (to_string(time.first) + ":");if(time.second < 10) //小于10要補0{cur += '0';}cur += to_string(time.second);res.push_back(cur); //組合結果return;}//嘗試當前每一種組合for(int i = index; i < 10; i++){//超出范圍,舍棄該數據if(time.first > 11 || time.second > 59){continue;}pair<int, int> backUp = time;//前四個燈為小時if(i < 4){time.first += nToTime[i];}//后六個燈為分鐘else{time.second += nToTime[i];}DFS(res, num - 1, i + 1, time); //進入下一層搜索, 下次從第i + 1棧燈開始time = backUp; //回溯狀態}}vector<string> readBinaryWatch(int num) {vector<string> res;pair<int, int> time(0, 0);DFS(res, num, 0, time);return res;} };

組合總數

給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的數字可以無限制重復被選取。

說明：

所有數字（包括 target）都是正整數。
解集不能包含重復的組合。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/combination-sum

和上面的思路一樣，不過此時由于數據可以無限被選取，所以搜索時下一步的位置還是從當前位置i開始，不需要繼續推進。(這道題目也可以當成完全背包，與動態規劃題解中的零錢問題II類似)

class Solution { public:void DFS(vector<int>& candidates, vector<vector<int>>& res, vector<int>& cur, int target, int sum, int index){//如果大于等于target，則不可再增加if(sum >= target){//如果和target相等則返回結果集if(sum == target){res.push_back(cur);}return;}//嘗試當前各種結果for(int i = index; i < candidates.size(); i++){//如果當前元素比target大,則不可能成立，直接跳過if(candidates[i] > target){continue;}cur.push_back(candidates[i]);DFS(candidates, res, cur, target, sum + candidates[i], i); //由于此時數據可以被無限選取，所以下一步的位置繼續從i開始搜索cur.pop_back(); //回溯}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if(candidates.empty()){return {};}vector<vector<int>> res;vector<int> cur;DFS(candidates, res, cur, target, 0, 0);return 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
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

照著模板就可以寫出來

class Solution { public:void DFS(vector<vector<int>>& allRet, vector<int>& curRet, vector<int>& nums, vector<bool>& visited){//滿足條件則加入結果集if(curRet.size() == nums.size()){allRet.push_back(curRet);}for(int i = 0; i < nums.size(); i++){//跳過以訪問數字if(visited[i] == false){continue;}//記錄當前結果curRet.push_back(nums[i]);visited[i] = false;//進行下一步的搜索DFS(allRet, curRet, nums, visited);//回溯curRet.pop_back();visited[i] = true;}}vector<vector<int>> permute(vector<int>& nums) {if(nums.empty()){return {};}vector<vector<int>> allRet;vector<int> curRet;vector<bool> visited(nums.size(), true);DFS(allRet, curRet, nums, visited);return allRet;} };

活字印刷

你有一套活字字模 tiles，其中每個字模上都刻有一個字母 tiles[i]。返回你可以印出的非空字母序列的數目。

注意：本題中，每個活字字模只能使用一次。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/letter-tile-possibilities

全排列的變形，此時變為處理字符串，并且返回任意可以印出的組合

1.當前組合不為空, 則插入set中

2.繼續給當前組合拼接新的組合，嘗試拼接tiles每一個位置的字符

3.如果當前位置已在組合中出現過，跳過該位置，否則標記當前位置，繼續拼接更長的組合

4.回溯，嘗試組合其它位置，返回

class Solution { public:void DFS(unordered_set<string>& set, vector<bool>& visited, string& tiles, string cur){//結果不為空則記錄下來if(!cur.empty()){set.insert(cur);}for(int i = 0; i < tiles.size(); i++){//如果當前字模已經用過, 則跳過本輪if(visited[i] == false){continue;}//記錄當前位cur.push_back(tiles[i]);visited[i] = false;//查找下一位DFS(set, visited, tiles, cur);//回溯, 繼續嘗試其他組合visited[i] = true;cur.pop_back();}}int numTilePossibilities(string tiles) {if(tiles.empty()){return 0;}unordered_set<string> set; //結果集, 去重vector<bool> visited(tiles.size(), true); //標記矩陣DFS(set, visited, tiles, "");return set.size();} };

N皇后

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

上圖為 8 皇后問題的一種解法。

給定一個整數 n，返回所有不同的 n 皇后問題的解決方案。

每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/n-queens

具體思路看注釋，主要就是嘗試所有排列組合，并判斷行，列，左右對角線是否存在其他皇后，然后將所有符合條件的結果保存下來即可。

class Solution { public:void DFS(vector<vector<pair<int, int>>>& allRes, vector<pair<int, int>>& curRes, int curRow, int n){//此時說明已經走完, 記錄結果if(curRow == n){allRes.push_back(curRes);}for(int i = 0; i < n; i++){//如果當前符合規則, 則繼續, 如果不符合直接忽略if(isVaild(curRes, curRow, i)){//記錄當前行位置curRes.push_back(make_pair(curRow, i));//查找下一行DFS(allRes, curRes, curRow + 1, n);//回溯curRes.pop_back();}}}bool isVaild(vector<pair<int, int>>& curRes, int row, int col){//判斷當前位置是否合法, 各皇后不能放在同一條直線上for(const pair<int, int>& cur : curRes){if(cur.first == row //判斷當前行|| cur.second == col //判斷當前列|| cur.first + cur.second == row + col //判斷左對角線|| cur.first - cur.second == row - col) //判斷右對角線{return false;}}return true;}//將坐標結果轉換為字符串的棋盤vector<vector<string>> resToString(vector<vector<pair<int, int>>>& allRes, int n){vector<vector<string>> res;for(const vector<pair<int, int>>& cur : allRes){vector<string> curRes(n, string(n, '.')); //初始化棋盤for(const pair<int, int>& pos : cur) //將皇后放入棋盤中{curRes[pos.first][pos.second] = 'Q';}res.push_back(curRes); //保存結果}return res;}vector<vector<string>> solveNQueens(int n) {vector<vector<pair<int, int>>> allRes;vector<pair<int, int>> curRes;DFS(allRes, curRes, 0, n);return resToString(allRes, n);} };

N皇后II

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

上圖為 8 皇后問題的一種解法。

給定一個整數 n，返回 n 皇后不同的解決方案的數量。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/n-queens-ii

和上題思路一樣，因為只需要返回解決方案的數量，所以不再保存結果，對符合條件的情況進行計數即可。

class Solution { public:void DFS(vector<pair<int, int>>& curRes, int curRow, int n, int& count){//此時不需要保存結果, 計數就行if(curRow == n){++count;}for(int i = 0; i < n; i++){//如果當前符合規則, 則繼續, 如果不符合直接忽略if(isVaild(curRes, curRow, i)){//記錄當前行位置curRes.push_back(make_pair(curRow, i));//查找下一行DFS(curRes, curRow + 1, n, count);//回溯curRes.pop_back();}}}bool isVaild(vector<pair<int, int>>& curRes, int row, int col){//判斷當前位置是否合法, 各皇后不能放在同一條直線上for(const pair<int, int>& cur : curRes){if(cur.first == row //判斷當前行|| cur.second == col //判斷當前列|| cur.first + cur.second == row + col //判斷左對角線|| cur.first - cur.second == row - col) //判斷右對角線{return false;}}return true;}int totalNQueens(int n) {vector<pair<int, int>> curRes;int count = 0;DFS(curRes, 0, n, count);return count;} };

總結

以上是生活随笔為你收集整理的高级数据结构与算法 | 回溯算法（Back Tracking Method）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。