C++

$\color{#cc33ff}{— > 算法基础课题解}$

DFS（深度优先搜索）（一个非常执着的人，我们学习的好榜样）:

在一个位置只要有路，就一直走到最深处知道无路可走，再退回上一步，看再上一步的位置能不能换个方向继续往下走。

$图解：$

$code1:$

#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N]; // 存储所有的方案数
bool st[N]; // 开一个bool数组表示当前点是否被用过，bool数组等于true的话，表示当前点被用过了

void dfs(int u) {
    if (u == n) { // 所有位置已经填满（叶节点）
        for (int i = 0; i < n; i ++) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++) {
        if (!st[i]) { // 如果没有被用过
            path[u] = i;
            st[i] = true;
            dfs(u + 1); // 到下一层循环
            st[i] = false; // 恢复原始状态
        }
    }
}
int main() {
    cin >> n;

    dfs(0);

    return 0;
}

$code2:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int path[10];
bool st[10];

void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i ++) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++) 
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }

}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}