大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
回溯法
百度百科：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步又一次选择，这样的走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
做完以下几题，应该会对回溯法的掌握有非常大帮助
N-Queens http://oj.leetcode.com/problems/n-queens/
N-Queens II http://oj.leetcode.com/problems/n-queens-ii/
Generate Parentheses http://oj.leetcode.com/problems/generate-parentheses/
N-Queens
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
![N-Queens And N-Queens II [LeetCode] + Generate Parentheses[LeetCode] + 回溯法](http://img-my.csdn.net/uploads/201405/08/1399513745_7164.png)
![N-Queens And N-Queens II [LeetCode] + Generate Parentheses[LeetCode] + 回溯法](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
经典的八皇后问题的扩展，利用回溯法，
（1）从第一列開始试探性放入一枚皇后
（2）推断放入后棋盘是否安全，调用checkSafe()推断
（3）若checkSafe()返回true，继续放下一列，若返回false，回溯到上一列，又一次寻找安全位置
（4）遍历全然部位置，得到结果
class Solution {public: vector<vector<string> > solveNQueens(int n) { int *posArray = new int[n]; int count = 0; vector< vector<string> > ret; placeQueue(0, n, count, posArray, ret); return ret; } //检查棋盘安全性 bool checkSafe(int row, int *posArray){ for(int i=0; i < row; ++i){ int diff = abs(posArray[i] - posArray[row]); if (diff == 0 || diff == row - i) { return false; } } return true; } //放置皇后 void placeQueue(int row, int n, int &count, int *posArray, vector< vector<string> > &ret){ if(n == row){ count++; vector<string> tmpRet; for(int i = 0; i < row; i++){ string str(n, '.'); str[posArray[i]] = 'Q'; tmpRet.push_back(str); } ret.push_back(tmpRet); return; } //从第一列開始试探 for(int col=0; col<n; ++col){ posArray[row] = col; if(checkSafe(row, posArray)){ //若安全，放置下一个皇后 placeQueue(row+1, n, count, posArray, ret); } } }};
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
仅仅需计算个数count即可，略微改动
class Solution {public: int totalNQueens(int n) { int *posArray = new int[n]; int count = 0; vector< vector<string> > ret; placeQueue(0, n, count, posArray, ret); return count; } //检查棋盘安全性 bool checkSafe(int row, int *posArray){ for(int i=0; i < row; ++i){ int diff = abs(posArray[i] - posArray[row]); if (diff == 0 || diff == row - i) { return false; } } return true; } //放置皇后 void placeQueue(int row, int n, int &count, int *posArray, vector< vector<string> > &ret){ if(n == row){ count++; return; } //从第一列開始试探 for(int col=0; col<n; ++col){ posArray[row] = col; if(checkSafe(row, posArray)){ //若安全，放置下一个皇后 placeQueue(row+1, n, count, posArray, ret); } } }};
Generate Parentheses
刚做完N-QUEUE问题，受之影响，此问题也使用回溯法解决，代码看上去多了非常多
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> vec;
int count = 0;
int *colArr = new int[2*n];
generate(2*n, count, 0, colArr, vec);
delete[] colArr;
return vec;
}
//放置括弧
void generate(int n,int &count, int col, int *colArr, vector<string> &vec){
if(col == n){
++count;
string temp(n,'(');
for(int i = 0;i< n;++i){
if(colArr[i] == 1)
temp[i] = ')';
}
vec.push_back(temp);
return;
}
for(int i=0; i<2;++i){
colArr[col] = i;
if(checkSafe(col, colArr, n)){
//放置下一个括弧
generate(n, count, col+1, colArr, vec);
}
}
}
//检查安全性
bool checkSafe(int col, int *colArr, int n){
int total = n/2;
if(colArr[0] == 1) return false;
int left = 0, right = 0;
for(int i = 0; i<=col; ++i){
if(colArr[i] == 0 )
++left;
else
++right;
}
if(right > left || left > total || right > total)
return false;
else
return true;
}
};
google了下，http://blog.csdn.net/pickless/article/details/9141935 代码简洁非常多，供參考
class Solution {
public:
vector<string> generateParenthesis(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> ans;
getAns(n, 0, 0, "", ans);
return ans;
}
private:
void getAns(int n, int pos, int neg, string temp, vector<string> &ans) {
if (pos < neg) {
return;
}
if (pos + neg == 2 * n) {
if (pos == neg) {
ans.push_back(temp);
}
return;
}
getAns(n, pos + 1, neg, temp + '(', ans);
getAns(n, pos, neg + 1, temp + ')', ans);
}
};
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118294.html原文链接：https://javaforall.net
