02用DFS实现

#include<iostream>
using namespace std;

const int N = 100; //最多可以做100个数的全排列
int n; //让用户输入做n个数的全排列
int path[N]; //记录搜素的路径
bool flag[N]; //对被搜索过的数字做标记


void dfs(int v)
{
    if (v==n)
    {
        //写到第n个位置已经把数枚举完了
        for (int i = 0; i < n; i++) cout << path[i] <<" ";
        cout << endl;
        return;
    }
    //当v<n说明还没有填完
    for (int i = 1; i <= n; i++)
    {
        if (!flag[i])//数字i还没出现在之前的序列中
        {
            path[v] = i; //把数字i放到第v个位置上去
            flag[i] = true; //数字i用过了    
            dfs(v+1); //这个位置填上数了，再对下一个位置最深度优先遍历，这个dfs结束之后就把下面的路走完了，需要回溯了，需要回复现场，出去什么样回来什么样
            path[v] = 0;
            flag[i] = false;
            flag[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0); //从第0个位置开始，深度搜索遍历，第一层看第一个位置，第2层看第二个位置，第3层看第3个位置
    return 0;
}