搜索（二）回溯

一、題目總結(jié)

基礎(chǔ)問題

  • 46.全排列
  • 77.組合
  • 78.子集
  • 39.組合求和
  • 47.全排列 II（重復(fù)元素）
  • 90.子集 II（重復(fù)元素）
  • 40.組合總和II（重復(fù)元素）
  • 216.組合總和III
  • 113.路徑總和 II

應(yīng)用問題

  • 416.分割等和子集
  • 17.電話號碼的字母組合
  • 131.分割回文串
  • 93.復(fù)原IP地址
  • 79.單詞搜索
  • 51.N皇后（hard）
  • 37.解數(shù)獨（hard）

二、題目

解決?個回溯問題秆剪，實際上就是?個決策樹的遍歷過程钝的。過程大致是：

  • 找到問題的選擇列表允跑；
  • 選擇當(dāng)前的節(jié)點；
  • 往下一層繼續(xù)選擇喘落；
  • 返回到上層的時候规伐，會撤銷對當(dāng)前節(jié)點的選擇蟹倾。

代碼框架：

DFS和回溯的區(qū)別：

  • DFS會對訪問過的節(jié)點進行標(biāo)記匣缘，表示以后不再重復(fù)訪問該結(jié)點猖闪；
  • 而回溯則是選擇當(dāng)前的節(jié)點，往下一層繼續(xù)選擇肌厨；返回到上層的時候培慌，會撤銷對當(dāng)前節(jié)點的選擇，使其以后還可能被選擇柑爸。

46.全排列

思路：套用回溯算法的模版吵护，然后通過visited數(shù)組來排除在temp中已經(jīng)選擇過的數(shù)字。

回溯樹：樹中最底層的結(jié)點表鳍。

vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int>& nums, vector<bool> visited){
    if (temp.size() == nums.size()) {
        ans.push_back(temp);
        return;
    }
    for (int i=0; i<nums.size(); i++) { // 選擇列表
        if (visited[i])  continue;

        temp.push_back(nums[i]); // 做選擇
        visited[i] = true;
        backtrack(nums, visited); // 進入下一層做選擇
        temp.pop_back(); // 撤銷選擇
        visited[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<bool> visited(nums.size(), false);
    backtrack(nums, visited);
    return ans;
}

77.組合

思路：套用回溯算法的模版馅而，然后通過傳入一個 start 參數(shù)，來排除已經(jīng)選擇過的數(shù)字譬圣。

回溯樹：樹中第k層的結(jié)點瓮恭。

vector<vector<int>> ans;
vector<int> temp;
void backtrack(int n, int k, int start){
    if (temp.size() == k) {
        ans.push_back(temp);
    }
    for (int i=start; i<=n; i++) {
        temp.push_back(i);
        backtrack(n, k, i+1);
        temp.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    backtrack(n, k, 1);
    return ans;
}

78.子集

思路：套用回溯算法的模版，然后通過傳入一個 start 參數(shù)厘熟，來排除已經(jīng)選擇過的數(shù)字屯蹦。

回溯樹：樹中的所有結(jié)點。

vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int>& nums, int start){
    ans.push_back(temp);
    for (int i=start; i<nums.size(); i++) {
        temp.push_back(nums[i]);
        backtrack(nums, i+1);
        temp.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    backtrack(nums, 0);
    return ans;
}

39 組合總和

vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int>& nums, int target, int start){
    if (target < 0) return;
    if (target == 0) ans.push_back(temp);
    
    for (int i=start; i<nums.size(); i++) {
        temp.push_back(nums[i]);
        backtrack(nums, target-nums[i], i);
        temp.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    backtrack(candidates, target, 0);
    return ans;
}

47.全排列 II

重復(fù)原因：有 2 個或以上個相同的元素在回溯樹同一層被分別選擇绳姨。-> 剪枝登澜。
剪枝操作：首先排序數(shù)組；然后與同一層的前一個進行比較飘庄。

在本題中脑蠕，!visited[i-1]表示在同一層。

vector<vector<int>> ans;
vector<int> temp;

void backtrack(vector<int>& nums, vector<bool> visited){
    if (temp.size() == nums.size()) {
        ans.push_back(temp);
    }
    for (int i=0; i<nums.size(); i++) {
        if (visited[i]) continue;
        if (i!=0 && !visited[i-1] && nums[i]==nums[i-1]) continue; 
        
        temp.push_back(nums[i]);
        visited[i] = true;
        backtrack(nums, visited);
        temp.pop_back();
        visited[i] = false;
    }
    
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<bool> visited(nums.size(), false);
    backtrack(nums, visited);
    return ans;
}

90.子集 II

重復(fù)原因：有 2 個或以上個相同的元素在回溯樹同一層被分別選擇跪削。-> 剪枝空郊。
剪枝操作：首先排序數(shù)組份招；然后與同一層的前一個進行比較。

在本題中狞甚，i>start表示在同一層锁摔。

vector<vector<int>> ans;
vector<int> temp;
void backtracking(vector<int>& nums, int start){
    ans.push_back(temp);
    
    for (int i=start; i<nums.size(); i++) {
        if (i>start && nums[i] == nums[i-1]) {
            continue;
        }
        temp.push_back(nums[i]);
        backtracking(nums, i+1);
        temp.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    backtracking(nums, 0);
    return ans;
}

40.組合總和II

同樣，i>start表示在同一層哼审。

vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int>& nums, int target, int start){
    if (target < 0) return;
    if (target == 0) ans.push_back(temp);
    
    for (int i=start; i<nums.size(); i++) {
        if (i>start && nums[i]==nums[i-1]) {
            continue;
        }
        temp.push_back(nums[i]);
        backtrack(nums, target-nums[i], i+1);
        temp.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    backtrack(candidates, target, 0);
    return ans;
}

216.組合求和III

vector<vector<int>> ans;
vector<int> temp;
void backtrack(int k, int target,int start){
    if (target < 0 || k < 0 ) return;
    if (target == 0 &&  k == 0) {
        ans.push_back(temp);
        return;
    }
    for (int i=start; i<10; i++) { // 選擇列表
        temp.push_back(i); // 做選擇
        backtrack(k-1, target-i, i+1); // 去一層選擇
        temp.pop_back(); // 撤銷選擇
    }
}
vector<vector<int>> combinationSum3(int k, int target) {
    backtrack(k, target, 1);
    return ans;
}

113. 路徑總和 II

二叉樹中的路徑回溯問題谐腰，還是那個套路。

vector<vector<int>> ans;
vector<int> temp;
void backtrack(TreeNode* root, int sum){
    int v = root->val;
    temp.push_back(v);
    if (!root->left && !root->right && sum == v) {
        ans.push_back(temp);
    }else{
        if (root->left) backtrack(root->left, sum-v);
        if (root->right) backtrack(root->right, sum-v);
    }
    temp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
    if (!root) return ans;
    backtrack(root, sum);
    return ans;
}

416.分割等和子集

思路：找出所有子集涩盾，如果有子集的和為數(shù)組和的一半十气，則返回true。

為了優(yōu)化算法時間春霍，對重復(fù)的子集進行剪枝砸西。

bool ans = false;
void backtracking(vector<int>& nums, int start, int sum, int target){
    if (ans) return;
    if (sum > target) return;
    
    if (sum == target) {
        ans = true;
        return;
    }
    
    for (int i=start; i<nums.size(); i++) {
        // 剪枝（同一層）
        if (i>start && nums[i]==nums[i-1]) {
            continue;
        }
        sum += nums[i];
        backtracking(nums, i+1, sum, target);
        sum -= nums[i];
    }
}

bool canPartition(vector<int>& nums) {
    int s = accumulate(nums.begin(), nums.end(), 0);
    if (s % 2 != 0) return false;
    sort(nums.begin(), nums.end());
    backtracking(nums, 0, 0, s/2);
    
    return ans;
}

17.電話號碼的字母組合

思路：

map<char,string> mp={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},  {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
vector<string> ans;
string cur;

void backTracking(string digits, int idx){
    if (idx == digits.size()) {
        ans.push_back(cur);
        return;
    }
    
    string temp = mp[digits[idx]];
    for (int i=0; i<temp.size(); i++) {
        cur.push_back(temp[i]);
        backTracking(digits, idx+1);
        cur.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return ans;
    backTracking(digits, 0);
    return ans;
}

131.分割回文串

vector<vector<string>> ans;
vector<string> temp;
bool check(string s){
    int l = 0, r = s.size()-1;
    while (l<r) {
        if (s[l++] != s[r--])
            return false;
    }
    
    return true;
}
void backtrack(string s, int start){
    if (start >= s.size()) {
        ans.push_back(temp);
        return;
    }
    
    for (int i=start; i<s.size(); i++) {
        string subStr = s.substr(start, i-start+1);
        if (check(subStr)) {
            temp.push_back(subStr);
            backtrack(s, i+1);
            temp.pop_back();
        }
    }
}
vector<vector<string>> partition(string s) {
    backtrack(s, 0);
    return ans;
}

93.復(fù)原IP地址

思路：

vector<string> ans;
vector<string> path;
bool isValid(string ip){
    if(stoi(ip)>255) return false;
    if(ip.size()>=2 && ip[0] == '0') return false;
    
    return true;
}
void backtracking(string s){
    if (path.size() == 4) {
        if (s.empty()) {
            string str = path[0] + '.' + path[1] + '.' + path[2] + '.' +path[3];
            ans.push_back(str);
        }
    }else{
        for (int i=1; i<=3 && i<=s.length(); i++) {
            string ip = s.substr(0, i);
            if (isValid(ip)) {
                path.push_back(ip);
                backtracking(s.substr(i, s.length()-i));
                path.pop_back();
            }
        }
    }
}
vector<string> restoreIpAddresses(string s) {
    if (s.size() < 4) return ans;
    backtracking(s);
    return ans;
}

79.單詞搜索

思路：深度優(yōu)先搜索+簡單的回溯

bool backtracking(vector<vector<char>>& board, string word, int i, int j, int k, vector<vector<bool>>& visited){
    if (i<0 || i>=board.size() || j<0 || j>=board[0].size()) {
        return false;
    }
    if (board[i][j] != word[k] || visited[i][j]) {
        return false;
    }
    
    if (k == word.size()-1) {
        return true;
    }
    visited[i][j] = true;
    
    bool ans =  backtracking(board, word, i-1, j, k+1, visited) ||
    backtracking(board, word, i+1, j, k+1, visited) ||
    backtracking(board, word, i, j-1, k+1, visited) ||
    backtracking(board, word, i, j+1, k+1, visited);
    
    visited[i][j] = false;
    
    return ans;
}

bool exist(vector<vector<char>>& board, string word) {
    int m = board.size(), n = board[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (backtracking(board, word, i, j, 0, visited)) {
                return true;
            }
        }
    }
    return false;
}

51.N皇后

問題描述：任意兩個皇后都不能處于同一行、同一列或同一斜線上址儒。

其實還是那個思路芹枷，并不難，一半的代碼都在判斷當(dāng)前點能否放皇后莲趣。

vector<vector<string>> ans;
bool isValid(vector<string> ans1, int n, int row, int col){
    // 行不用檢查
    // 檢查列
    for (int i=0; i<n; i++) {
        if (ans1[i][col] != '.') return false;
    }
    // 檢查左上
    for (int i=row-1, j=col-1; (i>=0 && j>=0); i--, j--) {
        if (ans1[i][j] != '.') return false;
    }
    // 檢查右上
    for (int i=row-1, j=col+1; (i>=0 && j<n); i--, j++) {
        if (ans1[i][j] != '.') return false;
    }
    return true;
}
void backtrack(int n, vector<string>& board, int row){
    if (row == n) {
        ans.push_back(board);
        return;
    }
    for (int col=0; col<n; col++) {
        if (!isValid(board, n, row, col)) continue;
        board[row][col] = 'Q';
        backtrack(n, board, row+1); // 進入下一層選擇
        board[row][col] = '.';
    }
}
vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    backtrack(n, board, 0);
    return ans;
}

37. 解數(shù)獨

問題描述：每一行鸳慈、每一列、每一個粗線宮（3*3）內(nèi)的數(shù)字均含1-9喧伞，不重復(fù)走芋。給定數(shù)獨永遠(yuǎn)是 9x9 形式的。

思路：下一層是下一列潘鲫，如果列到尾了翁逞，就去下一行的第一個開始。

bool isValid(vector<vector<char>>& board, int r, int c, char ch){
    for (int i=0; i<9; i++) {
        if (board[r][i] == ch) return false;
        if (board[i][c] == ch) return false;
        if (board[r/3*3 + i/3][c/3*3 + i%3] == ch) return false;
    }
    return true;
}
bool backtrack(vector<vector<char>>& board, int i, int j){
    if (j == 9) return backtrack(board, i+1, 0); // 窮舉到最后一列
    if (i == 9) return true; // 找到一個可行解
    
    if (board[i][j] != '.') {
         // 如果有預(yù)設(shè)數(shù)字溉仑，不用我們窮舉
        return backtrack(board, i, j+1);
    }
    for (char ch = '1'; ch<='9'; ch++) {
        if (!isValid(board, i, j, ch)) continue;
        
        board[i][j] = ch;
        if (backtrack(board, i, j+1)) {
            // 如果找到一個可行解挖函，立即結(jié)束
            return true;
        }
        board[i][j] = '.';
    }
    // 窮舉完 1~9，依然沒有找到可行解彼念，此路不通挪圾，返回上一層。
    return false;
}
void solveSudoku(vector<vector<char>>& board) {
    backtrack(board, 0, 0);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末逐沙，一起剝皮案震驚了整個濱河市哲思，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌吩案，老刑警劉巖棚赔，帶你破解...
    沈念sama閱讀 207,113評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡靠益，警方通過查閱死者的電腦和手機丧肴，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,644評論 2贊 381
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來胧后，“玉大人芋浮，你說我怎么就攤上這事】强欤” “怎么了纸巷？”我有些...
    開封第一講書人閱讀 153,340評論 0贊 344
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長眶痰。 經(jīng)常有香客問我瘤旨，道長，這世上最難降的妖魔是什么竖伯？ 我笑而不...
    開封第一講書人閱讀 55,449評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任存哲，我火速辦了婚禮，結(jié)果婚禮上七婴，老公的妹妹穿的比我還像新娘祟偷。我一直安慰自己，他們只是感情好本姥，可當(dāng)我...
    茶點故事閱讀 64,445評論 5贊 374
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布肩袍。 她就那樣靜靜地躺著杭棵，像睡著了一般婚惫。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上魂爪，一...
    開封第一講書人閱讀 49,166評論 1贊 284
  • 城市分裂傳說
    那天先舷，我揣著相機與錄音，去河邊找鬼滓侍。 笑死蒋川，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的撩笆。 我是一名探鬼主播捺球，決...
    沈念sama閱讀 38,442評論 3贊 401
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼夕冲！你這毒婦竟也來了氮兵？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,105評論 0贊 261
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤歹鱼，失蹤者是張志新（化名）和其女友劉穎泣栈，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 43,601評論 1贊 300
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡南片，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,066評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年掺涛，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片疼进。...
    茶點故事閱讀 38,161評論 1贊 334
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡薪缆，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出伞广，到底是詐尸還是另有隱情矮燎，我是刑警寧澤，帶...
    沈念sama閱讀 33,792評論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布赔癌，位于F島的核電站诞外，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏灾票。R本人自食惡果不足惜峡谊，卻給世界環(huán)境...
    茶點故事閱讀 39,351評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望刊苍。 院中可真熱鬧既们，春花似錦、人聲如沸正什。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,352評論 0贊 19
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽婴氮。三九已至斯棒，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間主经，已是汗流浹背荣暮。 一陣腳步聲響...
    開封第一講書人閱讀 31,584評論 1贊 261
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留罩驻，地道東北人穗酥。 一個月前我還...
    沈念sama閱讀 45,618評論 2贊 355
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像惠遏，于是被迫代替她去往敵國和親砾跃。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 42,916評論 2贊 344