全排列（DFS和next_permutation解法）

从 n 个不同元素中任取m (m≤n) 个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m=n 时所有的排列情况叫全排列。

今天这道题目很简单就是给你一个整数 n ，计算 [1,n] 所有数字的排列组合。
输入格式
第一行输入一个整数n(1≤n≤10).

输出格式
第一行输出一个全排列的方案总数 m。

接下来按照字典序依次输出这 m 个排列。

排列的字典的比较方法和字符串一样，比如两个排列 a,b，从第一个数开始，找到第一个不同的数的位置为i，然后比较 a[i] 和b[i] 的大小，如果 a[i] 小的，那么 a 的字典序就小，否则 b 的字典序更小。

样例输入1

2

样例输出1

2
12
21

样例输入2

3

样例输出2

6
123
132
213
231
312
321

解法1： 直接用stl里的next_permutation(a,a+n)

#include<bits/stdc++.h>
using namespace std;
int n,a[20];
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
    
        a[i]=i+1;
    }
    int cnt=0;
    do{
    
        cnt++;
    }while(next_permutation(a,a+n));
    cout<<cnt<<endl;
    do{
    
        for(int i=0;i<n;i++){
    
            cout<<a[i];
        }
        cout<<endl;
    }while(next_permutation(a,a+n));
    return 0;
}

解法2： DFS
简单DFS题目，直接搜索就可以了。
每次从 1 - n1−n 选择一个前面没有使用过的数字，把前面使用过的数字进行标记。使用结束的时候要把前面标记过的数字进行释放。
这个时候你会发现输出的答案正好是按照字典序输出。其实也是在意料中，因为我们每次尝试的时候都是从最小的开始。
注意这里不能加上重复性剪枝，因为这里是排列，和搜索顺序有关。

#include<bits/stdc++.h>
using namespace std;
bool vis[20];
int n,m=1;
void dfs(int x,int y){
    
    if(x==n){
    
        printf("%d\n",y);
        return;
    }
    for(int i=1;i<=n;i++){
    
        if(!vis[i]){
    
            vis[i]=true;
            dfs(x+1,y*10+i);
            vis[i]=false;
        }
    }
}
int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++){
    
        m*=i;
    }
    printf("%d\n",m);
    dfs(0,0);  
}