题解 P1706 【全排列问题】

· · 题解

来波递归

附上AC代码

#include<bits/stdc++.h>
using namespace std;
int i,something[10086];
bool anything[10086];
int nothing(int n);
int main(){
    cin>>i;
    nothing(1);
}
int nothing(int n){
    if(n>=i+1){
        for(int j=1;j<=i;j++)
            printf("%5d",something[j]);//输出
        cout<<endl;
        return 0;
    }
    for(int j=1;j<=i;j++){
        if(anything[j])//判断是否选过
            continue;
        anything[j]=1;
        something[n]=j;
        nothing(n+1);//递归
        anything[j]=0;//回溯
    }
}

每次都输出一组数

一个循环枚举每一个数

举个栗子

输入4

递归n次：

第一次 第二次 第……次
something[1]=1 something[1]=1 ……
something[2]=2 something[2]=2 ……
something[3]=3 something[3]=4 ……
something[4]=4 something[4]=3 ……

AC愉快