从 nn 个不同元素中任取 m\ (m \le n)m (m≤n) 个元素，按照一定的顺序排列起来，叫做从 nn 个不同元素中取出 mm 个元素的一个排列。当 m=nm=n 时所有的排列情况叫全排列。
今天这道题目很简单就是给你一个整数 nn ，计算 [1,n][1,n] 所有数字的排列组合。

输入格式

第一行输入一个整数 n ( 1 \le n \le 10)n(1≤n≤10).

输出格式

第一行输出一个全排列的方案总数 mm。
接下来按照字典序依次输出这 mm 个排列。
排列的字典的比较方法和字符串一样，比如两个排列 a,ba,b，从第一个数开始，找到第一个不同的数的位置为 ii，然后比较 a[i]a[i] 和 b[i]b[i] 的大小，如果 a[i]a[i] 小的，那么 aa 的字典序就小，否则 bb 的字典序更小。

样例输入1

2

样例输出1

2
12
21

样例输入2

3

样例输出2

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

开始错用了 重复性剪枝，

  1. void dfs(int s, int cnt, int pos) {
  2.     ...
  3.     ...
  4.     for (int i = pos; i <= n; i++) {
  5.         if (!xuan[i]) {
  6.             xuan[i] = true;
  7.             dfs(s + a[i], cnt + 1, i + 1); // i + 1 表示从上一次选取的位置后面开始选
  8.             xuan[i] = false;
  9.         }
  10.     }
  11. }

然而这里是全排列 1 2 3 和 3 2 1 是不一样的，不能用重复性剪枝，对于那些更本不关注选出来的顺序可以用重复性剪枝

全排列的结果就是阶乘，当时没想到！就用集合set来存储数据，迭代器操作集合元素时 要通过 * (解引用运算符)

标程

#include <iostream>
using namespace std;
int n;
bool vis[10];

void dfs(int num, int cnt) {
    if (cnt == n) {
        cout << num << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            dfs(num * 10 + i, cnt + 1);
            vis[i] = false;
        }
    }
}

int main() {
    int ans = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ans *= i;
    }
    cout << ans << endl;
    dfs(0,0);
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
int n, ans;
bool vis[11];
set<string> st;
void dfs(string s, int cnt) {
    if (cnt == n) {
        ans++;
        st.insert(s);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            dfs(s + char('0' + i), cnt + 1);
            vis[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs("", 0);
    cout << ans << endl;
    for (set<string>::iterator it = st.begin(); it != st.end(); it++) {
        cout << *it << endl;
    }
    return 0;
}