搜索（二）回溯

一、题目总结

基础问题

• 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);
}