思想：深搜会一条路走到黑，把所有的位置都填满，如下图中的路径1：

代码——重点在dfs函数：

#include <iostream>
using namespace std;const int N = 7;
int n;// st[i]代表i这个数有没有被用过; 比如st[1]=false代表1这个数没有被用过
// path[i]代表当前i位置上放的数; 比如path[0]=1代表0这个位置上放的是数1
bool st[N + 10]; // bool数组的全部元素都会初始化为false
int path[N + 10];// u代表第几个位置, 范围为[0,u-1]
void dfs(int u)
{// 如果已经遍历到第3个位置，代表0,1,2三个位置都已经放好数字，那么输出该方案即可if (u == n){for (int i = 0; i < n; i ++ )cout << path[i] << " ";cout << endl;// 该方案输出完毕后就回溯return;}for (int i = 1; i <= n; i ++ ){// 如果1这个数没有被用过if (!st[i]){// 那么当前这个位置放1path[u] = i;// 并记录1这个数已经被用过了st[i] = true;// 然后遍历下一个位置dfs(u + 1);// 下一个位置放好数后，要恢复现场st[i] = false;}}
}int main()
{cin >> n;// n为3时，有三个数字，三个位置// dfs(0)代表第0个位置dfs(0);return 0;
}