回溯

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

77. 组合

  • 基本

    class Solution {
    private:
      vector > ans; // 存放符合条件结果的集合
      vector path; // 用来存放符合条件结果
      void backtracking(int n, int k, int startIndex) {
          if (path.size() == k) {
              result.push_back(path);
              return;
          }
          for (int i = startIndex; i <= n; i++) {
              path.push_back(i); // 处理节点 
              backtracking(n, k, i + 1); // 递归
              path.pop_back(); // 回溯,撤销处理的节点
          }
      }
    public:
      vector> combine(int n, int k) {
          backtracking(n, k, 1);
          return ans;
      }
    };
  • 剪枝:最后几个没有必要去遍历

    设当前为i,遍历到n,还需要k-path.size()个元素,目前最多有n-i+1个元素那么n- i+1>=k-path.size()

    ```cpp
    class Solution {
    private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
    if (path.size() == k) {
    result.push_back(path);
    return;
    }
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
    path.push_back(i); // 处理节点
    backtracking(n, k, i + 1);
    path.pop_back(); // 回溯,撤销处理的节点
    }
    }
    public:
    vector<vector<int>> combine(int n, int k) {
    backtracking(n, k, 1);
    return result;
    }
    };

216. 组合总和 III

和题目77一样,只是多了一个限制求和条件。加入一个求和过大的剪枝

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(int k, int n, int startIndex, int curSum) {
        if (curSum > n) {
            return;
        }
        if(path.size()==k) {
            if(curSum==n) ans.push_back(path);
            return;
        }
        for(int i=startIndex; i<=9+1-(k-path.size());i++) {
            curSum+=i;
            path.push_back(i);
            backtracking(k, n, i+1, curSum);
            path.pop_back();
            curSum-=i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, 0);
        return ans;
    }
};

17. 电话号码的字母组合

定义一个map,然后回溯搜索即可

这里的index是树的深度,之前的statIndex是数组序列

class Solution {
private:
    const string leeterMap[10] = {
        "",  //0
        "",  //1
        "abc",  //2
        "def",  //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs",  //7
        "tuv",  //8
        "wxyz"  //9
    };
public:
    vector<string> ans;
    string path;
    void backtracking(const string &digits, int index) {
        // 递归终止
        if(index == digits.size()) {
            ans.push_back(path);
            return;
        }
        // 当前节点操作
        int digit = digits[index]-'0';  // 数字int
        string letters = leeterMap[digit]; // 数字对应的字符集
        for(int i=0; i<letters.size();i++) {
            path += letters[i];
            backtracking(digits,index+1);
            // 归
            path.pop_back();
        }

    }
    vector<string> letterCombinations(string digits) {
        // path.clear();
        // ans.clear();
        if(digits.size()==0) return {};
        backtracking(digits, 0);
        return ans;        
    }
};

39. 组合总和

做简单的剪枝

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtraking(vector<int>& candidates, int target, int startIndex, int curSum) {
        // 终止条件
        if(curSum==target) {
            ans.push_back(path);
            return;
        }
        // 当前广度
        for(int i=startIndex; i<candidates.size()&& curSum+candidates[i]<=target;i++) {
            curSum+=candidates[i];
            path.push_back(candidates[i]);
            backtraking(candidates, target, i, curSum);
            curSum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        if(candidates[0]>target) return ans;
        backtraking(candidates, target, 0, 0);
        return ans;
    }
};

40. 组合总和 II

去重说明:

选择i>startIndex && candidates[i]==candidates[i-1],不需要用used数组或者哈希表

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int curSum, int startIndex) {
        if(curSum == target) {
            ans.push_back(path);
            return;
        }
        for(int i=startIndex; i<candidates.size() && candidates[i]+curSum<=target;i++) {
            if(i>startIndex && candidates[i]==candidates[i-1]) continue;  //去重,当i不是最开始的startIndex时候开始
            curSum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, curSum, i + 1); // 和39.组合总和的区别1,这里是i+1,每个数字在每个组合中只能使用一次
            curSum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        if(candidates[0]>target) return ans;
        backtracking(candidates, target, 0, 0);
        return ans;
    }
};

131. 分割回文串

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    // 判断子串是否是回文
    bool isPalindrome(const string& s, int start, int end) {
        for(int i=start, j=end;i<=j;i++,j--) {
            if(s[i]!=s[j]) return false;
        }
        return true;
    }
    void backtracking(const string& s, int startIndex) {
        if(startIndex >= s.size()) {
            // 可能是整个都是,这时候startIndex=s.size()+1
            ans.push_back(path);
            return;
        }
        for(int i=startIndex; i<s.size(); i++) {
            if(isPalindrome(s, startIndex, i)) {
                // 如果当前的分割是回文
                string sub = s.substr(startIndex, i-startIndex+1);
                path.push_back(sub);

            } else {
                continue;
            }
            backtracking(s, i+1);
            path.pop_back();
        }
    } 
    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return ans;
    }
};

93. 复原 IP 地址

采用插入逗号的方式,如果新建一个path每次要判断路径长度

class Solution {
public:
    vector<string> ans;
    bool isValid(const string &s, int start, int end) {
         if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
    void backtracking(string &s, int startIndex, int pointNum) {
        if(pointNum==3) {
            if(isValid(s, startIndex, s.size()-1)) {
                ans.push_back(s);
            }
            return;
        }
        for(int i=startIndex; i<s.size();i++) {
            if(isValid(s, startIndex, i)) {
                s.insert(s.begin()+i+1, '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i+2, pointNum);
                pointNum--;
                s.erase(s.begin()+i+1);  // 回溯删掉逗点
            } else {
                break;  // 当前不合法了,继续循环也是不合法。09 091
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backtracking(s, 0, 0);
        return ans;
    }
};

说明:子集问题和组合问题相似,就是添加path的时候,在递归最外层加入,就是首先要加入自己本身

78. 子集

组合是收集所有的叶节点,子集是收集所有的节点

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        ans.push_back(path);  // 加入自己
        if(startIndex == nums.size()) {
            return;
        }
        for(int i=startIndex; i<nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }
    }

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

90. 子集 II

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(vector<int>& nums, int startIndex) {
        ans.push_back(path);
        if(startIndex==nums.size()) {
            return;
        }
        for(int i=startIndex; i<nums.size();i++) {
            // 去重
            if(i>startIndex && nums[i]==nums[i-1]){
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return ans;
    }
};

491. 递增子序列

由于该序列是无序的,使用if(i>startIndex && nums[i]==nums[i-1]) continue;只能去重同一层的排序好的序列,因此必须使用used数组或者hash。错误如下:

输入:[1,2,3,1,1]

输出结果:[[1,2],[1,2,3],[1,3],[1,1],[1,1,1],[2,3],[1,1]]

预期结果:[[1,2],[1,2,3],[1,3],[1,1],[1,1,1],[2,3]]

  • 使用set去重

    class Solution {
    public:
      vector path;
      vector> ans;
      void backtracking(vector& nums, int startIndex) {
          // 加入本身
          if(path.size()>=2) {
              ans.push_back(path);
          }
          if(startIndex==nums.size()) {
              return;
          }
          unordered_set uset;  // 使用set对本层元素进行去重
          for(int i=startIndex; i0 && nums[i]>=path.back())) 
              backtracking(nums, i+1);
              path.pop_back();
    
          }
      }
      vector> findSubsequences(vector& nums) {
          if(nums.size()<2) return {};
          backtracking(nums, 0);
          return ans;
      }
    };
  • 使用数组去重

    class Solution {
    public:
      vector path;
      vector> ans;
      void backtracking(vector& nums, int startIndex) {
          // 加入本身
          if(path.size()>=2) {
              ans.push_back(path);
          }
          if(startIndex==nums.size()) {
              return;
          }
          int used[201] = {0}; // 这里使用数组来进行去重操作,题目说数值范围[-100, 100] 
          for(int i=startIndex; i0 && nums[i]>=path.back())) 
              backtracking(nums, i+1);
              path.pop_back();
    
          }
      }
      vector> findSubsequences(vector& nums) {
          if(nums.size()<2) return {};
          backtracking(nums, 0);
          return ans;
      }
    };

46. 全排列

排列问题就不再使用startIndex,因为是有序的, [1,2] 和 [2,1] 是两个集合

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(vector<int>& nums, vector<int>& used) {
        // 终止
        if(nums.size()==path.size()) {
            ans.push_back(path);
            return;
        }
        for(int i=0; i<nums.size();i++) {
            if(used[i]==1) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            used[i] = 0;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
            vector<int> used(nums.size(),0);
            backtracking(nums, used);
            return ans;
    }
};

47. 全排列 II

  • 使用set去重

    class Solution {
    public:
      vector path;
      set> ans;
    
      void backtracking(vector& nums, vector& used) {
          if(path.size()==nums.size()) {
              ans.insert(path);
              return;
          }
    
          for(int i=0; i> permuteUnique(vector& nums) {
          vector used(nums.size(),0);
          backtracking(nums, used);
          vector> res;
          res.assign(ans.begin(), ans.end());
          return res;
      }
    };
  • 使用数组去重,要先排序

    class Solution {
    public:
      vector path;
      vector> ans;
    
      void backtracking(vector& nums, vector& used) {
          if(path.size()==nums.size()) {
              ans.push_back(path);
              return;
          }
    
          for(int i=0; i0 && nums[i-1]==nums[i] && used[i-1]==0) {
                  continue;
              }
              // 使用过了
              if(used[i]==1) {
                  continue;
              }
              path.push_back(nums[i]);
              used[i] = 1;
              backtracking(nums, used);
              used[i] = 0;
              path.pop_back();
    
          }
      }
      vector> permuteUnique(vector& nums) {
          sort(nums.begin(), nums.end());
          vector used(nums.size(),0);
          backtracking(nums, used);
          return ans;
      }
    };

332. 重新安排行程

class Solution {
public:
    unordered_map<string,map<string, int>> targets;  //unordered_map<出发机场, map<到达机场, 航班次数>> targets
    vector<string> result;
    bool backtracking(int ticketNum ) {
        // 到达的地方为机票数目+1
        if(result.size()==ticketNum ) {
            return true;
        }
        // 遍历,key是result的倒数第一个
        // pair<const string, int>& target的写法要注意,改变target'y
        for(pair<const string, int>& target :targets[result[result.size()-1]]) {
            if(target.second > 0 ) {
                // 还有
                result.push_back(target.first);
                target.second--;
                if(backtracking(ticketNum)) return true;
                result.pop_back();
                target.second++;
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(vector<string> vec : tickets) {
            targets[vec[0]][vec[1]]++;  // 记录映射关系
        }
        result.push_back("JFK");
        backtracking(tickets.size()+1);
        return result;
    }
};

51. N 皇后

class Solution {
public:
    vector<vector<string>> ans;
    bool isValid(int row, int col, int n, const vector<string> board){
        // 列检测
        for(int i=0;i<row;i++) {
            if(board[i][col] == 'Q'){
                return false;
            }
        }
        // 行检测不需要 每一次一行只会有一个
        // 45°
        for(int i=row-1, j=col-1;i>=0 && j>=0 ;i--,j--) {
            if(board[i][j] == 'Q'){
                return false;
            }
        }
        // 135°
        for(int i=row-1, j=col+1;i>=0 && j<n ;i--,j++) {
            if(board[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    void backtracking(int n, int row, vector<string> &board) {
        if(row == n) {
            ans.push_back(board);
        }
        // 遍历每一列
        for(int col=0; col<n; col++) {
            if(isValid(row, col, n, board)) {
                board[row][col] = 'Q';
                backtracking(n, row+1,board);
                board[row][col] = '.';
            }
        }

    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n,'.'));
        backtracking(n,0,board);
        return ans;
    }
};

37. 解数独

  • 本题递归不用终止条件,解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
  • 因为如果一行一列确定下来了,这里尝试了9个数都不行,说明这个棋盘找不到解决数独问题的解!那么会直接返回, 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去!
class Solution {
public:
    bool isValid(vector<vector<char>>& board, int row, int col, char val){
        for (int i = 0; i < 9; i++) { // 判断行里是否重复
            if (board[row][i] == val) {
                return false;
            }
        }
        for (int j = 0; j < 9; j++) { // 判断列里是否重复
            if (board[j][col] == val) {
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val ) {
                    return false;
                }
            }
        }
        return true;
    }
    bool backtracking(vector<vector<char>>& board) {
        for(int i=0; i<board.size();i++) {
            for(int j=0; j<board[0].size();j++) {
                if(board[i][j] != '.') continue;
                for(char k='1'; k<='9'; k++) {
                    if(isValid(board, i, j, k)) {
                        board[i][j] = k;
                        if(backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;  // 9个数都试完了,都不行,那么就返回false
            }
        }
        return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇