题目地址：

https://www.acwing.com/problem/content/844/

给定一个正整数$n$，生成$1\sim n$的全排列，按照字典序输出。

输入格式：
共一行，包含一个整数$n$。

输出格式：
按字典序输出所有排列方案，每个方案占一行。

数据范围：
$1\le n\le 7$

思路是DFS。从$1$到$n$逐个进行枚举，每次枚举记录下已经用过的数，将当前枚举的数加入列表后DFS进入下一层。代码如下：

#include <iostream>
#include <vector>
using namespace std;void dfs(int n, vector<int>& v, bool used[]) {if (v.size() == n) {for (int i = 0; i < n; i++) cout << v[i] << ' ';cout << endl;return;}for (int i = 0; i < n; i++) {if (!used[i]) {v.push_back(i + 1);used[i] = true;dfs(n, v, used);v.pop_back();used[i] = false;}}
}int main() {int n;cin >> n;bool used[n];memset(used, false, sizeof used);vector<int> v;dfs(n, v, used);return 0;
}

时间复杂度$O(nn!)$，空间$O(n)$。