C++ 深度优先搜索实现数字全排列 (无重复数字)

C++ 深度优先搜索实现数字全排列 (无重复数字)

问题描述:

输出自然数 1~n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复数字。

输入格式:

1 <= n <= 9

输出格式:

由 1~n 组成的所有不重复的数字序列。每行一个序列

输入样例:

3

输出样例:

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

算法思路:

深度优先搜索 (DFS) + 回溯

1. 用一个布尔型数组 book[]，book[i] 表示数字 i 是否被使用过。初始化为 false。

2. 用一个整型数组 a[]，a[step] 表示当前排列中第 step 个位置放哪个数字。

3. 从第一个位置开始，枚举还没有被使用过的数字，如果当前位置已经填了一个数字，就进入下一个位置。如果当前位置没有填数，则将没有被使用过的数字依次尝试填入，并递归到下一个位置。

4. 递归结束条件是当前位置已经填满，即 step > n。

5. 输出当前排列。

6. 回溯，将当前位置的数字清空，并把它的状态改为未使用过的状态，即 book[a[step]] = false。

7. 注意：在 for 循环中，每次枚举的是所有没有被使用过的数字，而不是从 1 到 n。否则会输出重复的排列。

C++ 代码:

#include <iostream>
using namespace std;

int n;
bool book[10]; // 标记数字是否被使用
int a[10];     // 存储排列结果

void dfs(int step) {
    if (step > n) { // 递归结束条件：所有位置都填满了
        for (int i = 1; i <= n; i++) {
            cout << a[i] << ' ';
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) { // 枚举所有没有被使用过的数字
        if (!book[i]) { // 如果数字 i 没有被使用
            a[step] = i; // 将数字 i 填入当前位置
            book[i] = true; // 标记数字 i 已被使用
            dfs(step + 1); // 递归到下一个位置
            book[i] = false; // 回溯：将数字 i 的状态恢复为未使用
        }
    }
}

int main() {
    cin >> n;
    dfs(1); // 从第一个位置开始搜索
    return 0;
}