题目链接

全排列

描述:

输入一个自然数N(1<=N<=9),从小到大输出用1~N组成的所有排列,也就说全排列。例如输入3则输出
123
132
213
231
312
321

输入格式:

输入一个自然数N(1<=N<=9)

输出格式:

N的全排列,每行一个

输入样例:

3

输出样例:

123
132
213
231
312
321

代码:

#include<bits/stdc++.h>
using namespace std;
int a[10],book[10],n;//全局变量在不赋值之前默认是零 
void dfs(int step){//step表示站在第几个盒子前面 
    int i;
    if(step==n+1){//如果站在第n+1个盒子前,代表之前的盒子都装满了 
        for(i=1;i<=n;i++){
            printf("%d",a[i]);//输出一种排列 
        }
        printf("\n");
        return;//结束这次递归,并返回最近一次调用 
    }
    for(i=1;i<=n;i++){
        if(book[i]==0){//表示扑克牌在手上 
            a[step] = i;//将第i个扑克牌放到第step个盒子里 
            book[i] = 1;//表示扑克牌已经不再手上 
            dfs(step+1);//走到下一个盒子前 
            book[i] = 0;
            //将之前的扑克牌收回,表示前面的盒子所有可能性已经全部结束 
        }
    }
    return;
}
int main(){
    scanf("%d",&n);
    dfs(1);//站在一号盒子前 
    return 0;
}

解析:

利用DFS(深度优先搜索),每次调用自己,并判断几号扑克牌在手中,那个盒子是空着的。最后将其放入盒子中。


一只小菜鸡