[数据结构与算法]2021-09-17 回溯算法 |？？？

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

组合无序，排列有序

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

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

组合

class Solution {
public:
	vector<vector<int>> res;
	vector<int> path;
	void backTrack(int n,int k,int starter){
		if(path.size()==k){
			res.push_back(path);
			return;
		}
		for(int i=starter;i<=n;i++){//
			path.push_back(i);
			backTrack(n,k,i+1);
			path.pop_back();//回溯撤销，进入下一层for循环
		}
	}
    vector<vector<int>> combine(int n, int k) {
		//res.clear();
		//path.clear();
		backTrack(n,k,1);
		return res;
    }
};

优化：

for(int i=starter;i<=  n-(k-path.size())+1  ;i++){

组合总和 III

class Solution {
public:
	vector<vector<int>> res;
	vector<int> path;
	void backTrack(int n,int k,int sum,int starter){
		if(sum>n){
			return;//剪枝操作，总和大于目标了就退出
		}
		if(path.size()==k){
			if(sum==n){
				res.push_back(path);
			}
			return;
		}
		for(int i=starter;i<=9;i++){//固定1-9
			sum+=i;
			path.push_back(i);
			backTrack(n,k,sum,i+1);
			sum-=i;
			path.pop_back();//回溯撤销，进入下一层for循环
		}
	}
    vector<vector<int>> combinationSum3(int k, int n) {
		res.clear(); // 可以不加
        path.clear();
        backTrack(n,k,0,1);
		return res;
    }
};

电话号码的字母组合

class Solution {
public:
	string phoneNums[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
	string s;
	void backTrack(string& digits,int index){
		//递归到“23”大小就可以塞进去
		if(index==digits.size()){
			res.push_back(s);
			return;
		}
		//先处理好数据
		int digit=digits[index]-'0';//递归深度，转int
		string letters=phoneNums[digit];//for宽度
		//回溯
		for(int i=0;i<letters.size();i++){
			s.push_back(letters[i]);
			backTrack(digits,index+1);
			s.pop_back();
		}
	}
	vector<string> letterCombinations(string digits) {
		if(digits.size()==0){
			return res;
		}
		backTrack(digits,0);
		return res;
    }
};

N 皇后

class Solution {
public:
	vector<vector<string>> res;
	void backTrack(int n,int row,vector<string>& chessB){
		if(row==n){
			res.push_back(chessB);
			return;
		}
		for(int col=0;col<n;col++){
			if(isValid(row,col,chessB,n)){
				chessB[row][col]='Q';
				backTrack(n,row+1,chessB);
				chessB[row][col]='.';
			}
		}
	}
	bool isValid(int row,int col,vector<string>& chessB,int n){
		for(int i=0;i<row;i++){
			if(chessB[i][col]=='Q') return 0;
		}
		for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
			if(chessB[i][j]=='Q') return 0;
		}
		for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
			if(chessB[i][j]=='Q') return 0;
		}
		return 1;
	}
    vector<vector<string>> solveNQueens(int n) {
		vector<string> chessB(n,string(n,'.'));
		backTrack(n,0,chessB);
		return res;
    }
};

解数独

class Solution {
public:
	bool backTrack(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(backTrack(board)) return 1;
						board[i][j]='.';
					}
				}
				return 0;
			}
		}
        return 1;
	}
    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 0;
		}
		for(int j=0;j<9;j++){
			if(board[j][col]==val) return 0;
		}
		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 0;
            }
        }
    }
		return 1;
	}
    void solveSudoku(vector<vector<char>>& board) {
		backTrack(board);
    }
};