代码

发布日期: 2022-07-08

更新日期: 2022-07-09

文章字数: 2k

阅读时长: 11 分

回溯算法

回溯算法适用题目

组合问题：N个数找K个数的集合。
切割问题：字符串切割N个子串。
子集问题：N个数的集合中有多少个子集。
排列问题：N个数全排列。

棋盘问题：数独与N皇后等。

leetcode：77

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(int n,int k,int index){
  if(path.size()==k){
      result.push_back(path);
      return;
  }
  for(int i=index;i<=n;i++){
      path.push_back(i);
      bt(n,k,i+1);
      path.pop_back();
  }
}
vector<vector<int>> combine(int n, int k) {
  result.clear();
  path.clear();
  bt(n,k,1);
  return result;
}
};

leetcode：215

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(int sum,int index,int k,int n){
  if(sum>n) return;
  if(sum==n&&path.size()==k){
      result.push_back(path);
      return;
  }
  for(int i=index;i<=9;i++){
      path.push_back(i);
      bt(sum+i,i+1,k,n);
      path.pop_back();
  }
}
vector<vector<int>> combinationSum3(int k, int n) {
  result.clear();
  path.clear();
  bt(0,1,k,n);
  return result;
}
};

leetcode：17

class Solution {
public:
vector<string>path;
string temp;
string mz[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void bt(string digits,int num,int n){
  if(num==n){
      path.push_back(temp);
      return;
  }
  int number=digits[num]-'0';
  for(int i=0;i<mz[number].size();i++){
      temp.push_back(mz[number][i]);
      bt(digits,num+1,n);
      temp.pop_back();
  }
}
vector<string> letterCombinations(string digits) {
  if(digits.size()==0) return path;
  bt(digits,0,digits.size());
  return path;
}
};

leetcode：39

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(vector<int> candidates, int target,int sum,int index){
  if(sum>target) return;
  if(sum==target){
      result.push_back(path);
      return;
  }
  for(int i=index;i<candidates.size();i++){
      path.push_back(candidates[i]);
      bt(candidates,target,sum+candidates[i],i);
      path.pop_back();
  }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  result.clear();
  path.clear();
  bt(candidates,target,0,0);
  return result;
}
};

leetcode：40

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(vector<int> candidates, int target,int sum,int index){
  if(sum>target) return;
  if(sum==target){
      result.push_back(path);
      return;
  }
  for(int i=index;i<candidates.size();i++){
      if(i>index&&candidates[i]==candidates[i-1]) continue;
      path.push_back(candidates[i]);
      bt(candidates,target,sum+candidates[i],i+1);
      path.pop_back();
  }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  result.clear();
  path.clear();
  sort(candidates.begin(),candidates.end());
  bt(candidates,target,0,0);
  return result;
}
};

leetcode：113

class Solution {
public:
vector<vector<string>>result;
vector<string>path;
void bt(string s,int index){
  if(s.size()<=index) {
      result.push_back(path);
      return;
  }
  for(int i=index;i<s.size();i++){
      if(isPar(s,index,i)){
          string str = s.substr(index,i-index+1);
          path.push_back(str);
      }else continue;
      bt(s,i+1);
      path.pop_back();
  }
}
bool isPar(string s,int left,int right){
  for(int i=left,j=right;i<j;i++,j--){
      if(s[i]!=s[j]){
          return false;
      }
  }
  return true;
}
vector<vector<string>> partition(string s) {
  bt(s,0);
  return result;
}
};

leetcode：93

class Solution {
public:
vector<string>path;
void bt(string &s,int index,int num){
  if(num==3){
      if(isValid(s,index,s.size()-1)){
          path.push_back(s);
      }
      return;
  }
  for(int i=index;i<s.size();i++){
      if(isValid(s,index,i)){
          s.insert(s.begin()+i+1,'.');
          bt(s,i+2,num+1);
          s.erase(s.begin()+i+1);
      }else break;
  }
}
bool isValid(string s,int st,int ed){
  if(st>ed) return false;
  if(s[st]=='0'&&st!=ed){
      return false;
  }
  int num=0;
  for(int i=st;i<=ed;i++){
      if(s[i]>'9'||s[i]<'0') return false;
      num=num*10+(s[i]-'0');
      if(num>255) return false;
  }
  return true;
}
vector<string> restoreIpAddresses(string s) {
  if(s.size()>12) return path;
  bt(s,0,0);
  return path;
}
};

leetcode：78

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(vector<int>& nums,int index){
  result.push_back(path);
  if(index>=nums.size()) return;
  for(int i=index;i<nums.size();i++){
      path.push_back(nums[i]);
      bt(nums,i+1);
      path.pop_back();
  }
}
vector<vector<int>> subsets(vector<int>& nums) {
  result.clear();
  path.clear();
  bt(nums,0);
  return result;
}
};

leetcode：90

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(vector<int>& nums,int index){
  result.push_back(path);
  if(index>=nums.size()) return;
  for(int i=index;i<nums.size();i++){
      if(i>index&&nums[i]==nums[i-1]) continue;
      path.push_back(nums[i]);
      bt(nums,i+1);
      path.pop_back();
  }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  result.clear();
  path.clear();
  sort(nums.begin(),nums.end());
  bt(nums,0);
  return result;
}
};

leetcode：491

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void bt(vector<int>& nums,int index){
  if(path.size()>=2){
      result.push_back(path);
  }
  int used[201]={0};
  for(int i=index;i<nums.size();i++){
      if((!path.empty()&&nums[i]<path.back())||used[nums[i]+100]==1) 
          continue;
      used[nums[i]+100]=1;
      path.push_back(nums[i]);
      bt(nums,i+1);
      path.pop_back();
  }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
  result.clear();
  path.clear();
  bt(nums,0);
  return result;
}
};

leetcode：46

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
bool vis[100]={false};
void bt(vector<int>& nums){
  if(path.size()==nums.size()){
      result.push_back(path);
      return;
  }
  for(int i=0;i<nums.size();i++){
      if(vis[i]==true) continue;
      vis[i]=true;
      path.push_back(nums[i]);
      bt(nums);
      path.pop_back();
      vis[i]=false;
  }
}
vector<vector<int>> permute(vector<int>& nums) {
  result.clear();
  path.clear();
  bt(nums);
  return result;
}
};

leetcode：47

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
bool vis[100]={false};
void bt(vector<int>& nums){
  if(path.size()==nums.size()){
      result.push_back(path);
      return;
  }
  for(int i=0;i<nums.size();i++){
      if(vis[i]==true||(i>0&&nums[i]==nums[i-1]&&vis[i-1]==true)) continue;
      vis[i]=true;
      path.push_back(nums[i]);
      bt(nums);
      path.pop_back();
      vis[i]=false;
  }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
  result.clear();
  path.clear();
  sort(nums.begin(),nums.end());
  bt(nums);
  return result;
}
};

leetcode：51

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到***的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
  if (row == n) {
      result.push_back(chessboard);
      return;
  }
  for (int col = 0; col < n; col++) {
      if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
          chessboard[row][col] = 'Q'; // 放置皇后
          backtracking(n, row + 1, chessboard);
          chessboard[row][col] = '.'; // 回溯，撤销皇后
      }
  }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
  int count = 0;
  // 检查列
  for (int i = 0; i < row; i++) { // 这是一个剪枝
      if (chessboard[i][col] == 'Q') {
          return false;
      }
  }
  // 检查 45度角是否有皇后
  for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
      if (chessboard[i][j] == 'Q') {
          return false;
      }
  }
  // 检查 135度角是否有皇后
  for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (chessboard[i][j] == 'Q') {
          return false;
      }
  }
  return true;
}
public:
  vector<vector<string>> solveNQueens(int n) {
      result.clear();
      std::vector<std::string> chessboard(n, std::string(n, '.'));
      backtracking(n, 0, chessboard);
      return result;
  }
};

leetcode：37

class Solution {
public:
bool bt(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(i,j,k,board)){
                  board[i][j]=k;
                  if(bt(board)) return true;
                  board[i][j]='.';
              }
          }
          return false;
      }
  }
  return true;
}
bool isValid(int row,int col,char val,vector<vector<char>>& board)
{
  for(int i=0;i<9;i++){
      if(board[row][i]==val) return false;
  }
  for(int i=0;i<9;i++){
      if(board[i][col]==val) return false;
  }
  int startrow=(row/3)*3;
  int startcol=(col/3)*3;
  for(int i=startrow;i<startrow+3;i++){
      for(int j=startcol;j<startcol+3;j++){
          if(board[i][j]==val) return false;
      }
  }
  return true;
}
void solveSudoku(vector<vector<char>>& board) {
  bt(board);
}
};

技巧

树层去重需要排序。
排列选数从0开始，维护vis数组。而组合从index开始。
字符串的回溯函数中，index就是当前位置，从index-i来表示判定子串的范围。

FFFfrance

http://ffffrance.github.io/2022/070860033.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 FFFfrance !

代码

动态规划

动态规划，及例题。

2022-07-09 代码

代码

面向对象思想

2022-07-02 面向对象思想

面向对象思想

回溯算法

回溯算法

回溯算法适用题目

leetcode：77

leetcode：215

leetcode：17

leetcode：39

leetcode：40

leetcode：113

leetcode：93

leetcode：78

leetcode：90

leetcode：491

leetcode：46

leetcode：47

leetcode：51

leetcode：37

技巧

你的赏识是我前进的动力