搜索（二）回溯

一、题目总结

基础问题

  • 46.全排列
  • 77.组合
  • 78.子集
  • 39.组合求和
  • 47.全排列 II（重复元素）
  • 90.子集 II（重复元素）
  • 40.组合总和II（重复元素）
  • 216.组合总和III
  • 113.路径总和 II

应用问题

  • 416.分割等和子集
  • 17.电话号码的字母组合
  • 131.分割回文串
  • 93.复原IP地址
  • 79.单词搜索
  • 51.N皇后（hard）
  • 37.解数独（hard）

二、题目

解决⼀个回溯问题，实际上就是⼀个决策树的遍历过程。过程大致是：

  • 找到问题的选择列表；
  • 选择当前的节点；
  • 往下一层继续选择；
  • 返回到上层的时候，会撤销对当前节点的选择。

代码框架：

DFS和回溯的区别：

  • DFS会对访问过的节点进行标记，表示以后不再重复访问该结点；
  • 而回溯则是选择当前的节点，往下一层继续选择；返回到上层的时候，会撤销对当前节点的选择，使其以后还可能被选择。

46.全排列

思路：套用回溯算法的模版，然后通过visited数组来排除在temp中已经选择过的数字。

回溯树：树中最底层的结点。

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 参数，来排除已经选择过的数字。

回溯树：树中第k层的结点。

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 参数，来排除已经选择过的数字。

回溯树：树中的所有结点。

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

重复原因：有 2 个或以上个相同的元素在回溯树同一层被分别选择。-> 剪枝。
剪枝操作：首先排序数组；然后与同一层的前一个进行比较。

在本题中，!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

重复原因：有 2 个或以上个相同的元素在回溯树同一层被分别选择。-> 剪枝。
剪枝操作：首先排序数组；然后与同一层的前一个进行比较。

在本题中，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.分割等和子集

思路：找出所有子集，如果有子集的和为数组和的一半，则返回true。

为了优化算法时间，对重复的子集进行剪枝。

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.复原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.单词搜索

思路：深度优先搜索+简单的回溯

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皇后

问题描述：任意两个皇后都不能处于同一行、同一列或同一斜线上。

其实还是那个思路，并不难，一半的代码都在判断当前点能否放皇后。

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. 解数独

问题描述：每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。给定数独永远是 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] != '.') {
         // 如果有预设数字，不用我们穷举
        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)) {
            // 如果找到一个可行解，立即结束
            return true;
        }
        board[i][j] = '.';
    }
    // 穷举完 1~9，依然没有找到可行解，此路不通，返回上一层。
    return false;
}
void solveSudoku(vector<vector<char>>& board) {
    backtrack(board, 0, 0);
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,839评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,543评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,116评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,371评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,384评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,111评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,416评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,053评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,558评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,756评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,324评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2赞 345