递归实现排列型枚举

题目：
把 这 n(n<10)个整数排成一行后随机打乱顺序，按字典序输出所有可能的次序。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=10010;

int path[N];//记录当前路径，当前的情况
bool s[N];//记录当前数字是否被用过。
int n;
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) cout<<path[i]<<" ";//如果走到了头那么就输出答案
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!s[i]){
        path[u]=i;
        s[i]=true;//注意这里是用过了标记的true；
        dfs(u+1);
        path[u]=0;//恢复现场，返回上一步，恢复上一步原来的样子
        s[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
}

n皇后问题

n皇后问题

有两种顺序可以枚举。
代码：

//按全排列的顺序搜索，时间复杂度，n*n!;
#include<bits/stdc++.h>
using namespace std;

const int N=20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];//记录有没有被放过皇后，列，主副对角线。

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) puts(g[i]);//如果符合输出答案
        puts("");
        return;
    }
    for(int i=0;i<n;i++){//按行搜索排列
        if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){//确保这一列、主对角线、副对角线上都没有被选过
            g[u][i]='Q';//这里u+i,n-u+i，表示截距。
            col[i]=dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            g[u][i]='.';//恢复现场
            col[i]=dg[u+i]=udg[n-u+i]=false;
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0);

}

枚举每一个格子的代码：

//按一个一个格子的顺序搜索，时间复杂度2的n方次，指数级别。
#include<bits/stdc++.h>
using namespace std;

const int N=20;
int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];

void dfs(int x,int y,int s){
    if(y>n) return;
    if(y==n) y=0,x++;//如果y超过了边界换行，行数加1，y直接到下一行开头为0；
    if(x==n){
        if(s==n){
            for(int i=0;i<n;i++) puts(g[i]);
            puts("");
        }
        return;
    }
    g[x][y]='.';
    //两种选择
    dfs(x,y+1,s);//1.不放皇后，直接递归到下一个，递归由里往外执行
    //2.放皇后，则判断是否放过
    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){//判断行列、住副对角线是否被放过皇后
        g[x][y]='Q';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';//恢复现场
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }

}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0,0,0);

}