对于回溯法的理论描述这个就不赘述了，可以参考下面几个文章：
https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html
https://blog.csdn.net/EbowTang/article/details/51570317
这里主要说一下回溯法基本写法和步骤（以八皇后问题为例）：
void queen(int now, int all){ //all = 8, row代表当前在规划第row行的皇后
for(int i = 1; i <= all; i++){
if(check_ok(now, i, all)){
arr[now][i] = 1; //表示第row行的皇后放在第i列
if(now == all) //这是最后一个皇后
++sum; //总方案数+1
else
queen(now+1, all); // 递归调用，摆放下一个
arr[now][i] = 0; //第now个皇后摆在这个位置的所有相关方案已经全部尝试完毕，恢复原貌
}
}
}
- 每层函数要循环枚举这次要做的事情的所有情况，例如，每次摆一个皇后进去的时候，要枚举它在这一行的所有可能位置（
for(int i = 1; i <= all; ++i)）
2.检查要做的事情的合理性,如检查第now个皇后摆放在这里会不会和已有的皇后冲突（check_ok(now, i, all)）
函数func的每一层递归一定会做一些事情，不会不做任何事情，如每次进入一层函数，一定会摆一个皇后进一个格子。(
arr[row] = i;)回溯法有递归的思想，可以以函数func的递归来写。（
queen(row+1, all);）每次退出函数时，一定要恢复操作前的状态(
arr[now][i] = 0;)
例一：N皇后问题（杭电OJ 2553 http://acm.hdu.edu.cn/showproblem.php?pid=2553）
这道题有个小trick，因为数据范围小N<=10，所以要提前计算好然后打表，否则会超时
#include <iostream>
#include <string.h>
using namespace std;
int arr[11][11];
int sum = 0;
bool check_ok(int row, int col, int all){
for(int i = 1; i < row; ++i) //同一列没有其他
if(arr[i][col] == 1)
return false;
for(int i = row - 1, j = col - 1; i >= 1 && j >= 1; --i, --j){ //左斜线
if(arr[i][j] == 1)
return false;
}
for(int i = row - 1, j = col + 1; i >= 1 && j <= all; --i, ++j){ //右斜线
if(arr[i][j] == 1)
return false;
}
return true;
}
void queen(int now, int all){
for(int i = 1; i <= all; i++){ //遍历所有情况
if(check_ok(now, i, all)){ //检查合理性
arr[now][i] = 1; //操作
if(now == all)
++sum; //结束
else
queen(now+1, all); //递归
arr[now][i] = 0; //还原操作
}
}
}
int res[11];
int main(){
int n;
for(int i = 1; i <= 10; ++i){
sum = 0;
memset(arr, 0, sizeof(int) * 11 * 11);
queen(1, i);
res[i] = sum;
}
while(1){
cin >> n;
if(n == 0)
break;
cout << res[n] << endl;
}
return 0;
}
写法2, 基本差不多，省点内存：
#include <iostream>
#include <string.h>
using namespace std;
int arr[11], sum = 0;
bool check_ok(int row, int i, int all){
for(int j = 1; j < row; ++j){
if(i == arr[j] || i - arr[j] == row - j || i - arr[j] == j - row)
return false;
}
return true;
}
void queen(int row, int all){
for(int i = 1; i <= all; ++i){
if(check_ok(row, i, all)){
arr[row] = i;
if(row == all)
++sum;
else
queen(row+1, all);
}
}
}
int res[11];
int main(){
int n;
for(int i = 1; i <= 10; ++i){
sum = 0;
memset(arr, 0, sizeof(int) * 11);
queen(1, i);
res[i] = sum;
}
while(1){
scanf("%d", &n);
if(n == 0)
break;
printf("%d\n", res[n]);
}
return 0;
}
例二：生成括号（LeetCode22 https://leetcode-cn.com/problems/generate-parentheses/description/）
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
class Solution {
public:
int left_right;
vector<string> res;
char* tmp;
vector<string> generateParenthesis(int n) {
left_right = 0;
tmp = new char[2 * n + 1];
memset(tmp, 0, sizeof(char) * (2 * n + 1));
generate(0, 2 * n);
delete tmp;
return res;
}
void save_str(){
res.push_back(string(tmp));
}
void generate(int now, int all){ //注意可行操作只有左右括号两种，因此没有循环，而是写了两次
tmp[now] = '('; //操作
++left_right;
if(now == all - 1)
;
else
generate(now+1, all); //递归调用
--left_right;
tmp[now] = 0; //还原操作
if(left_right > 0){ //只有此时左括号多于右括号时，才能加入右括号
--left_right;
tmp[now] = ')';
if(now == all - 1){
if(left_right == 0)
save_str();
}
else{
generate(now+1 ,all);
}
++left_right;
tmp[now] = 0;
}
}
};
例三：整数分解（PAT-A1103 https://www.patest.cn/contests/pat-a-practise/1103）
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
vector<int> arr;
vector<int> res;
int n, k, p;
int i = 1;
int goods[21];
int max_sum = 0;
bool do_print(int sum){
if(sum > max_sum){
max_sum = sum;
return true;
}
return false;
}
void func(int which, int volumn, int count, int sum){
for(int a = which; a >= 1; --a){ // 遍历所有情况
if(goods[a] <= volumn){
arr.push_back(a); //将a计算在内
sum += a; //所有因子的和
if(goods[a] == volumn && count - 1 == 0){
if(do_print(sum)){
res.clear();
res.assign(arr.begin(), arr.end());
}
}
else if(count > 0){
func(a, volumn - goods[a], count - 1, sum); //递归调用
}
sum -= a;
arr.pop_back(); //删除a
}
}
}
int main(){
cin >> n >> k >> p;
while(1){
int temp = 1;
for(int j = 0; j < p; ++j){
temp = temp * i;
}
if(temp > n)
break;
goods[i++] = temp;
}
i--;
func(i, n, k, 0);
if(res.empty()){
cout << "Impossible" << endl;
}
else{
int size = res.size();
cout << n << " = ";
for(int a = 0; a < size; a++){
cout << res[a] << "^" << p;
if(a != size - 1)
cout << " + ";
}
cout << endl;
}
return 0;
}
