02用DFS实现全排列

#include <iostream>
using namespace std;

const int N = 10; //能对10个数进行全排列，比如n=3，就是对123全排列，N是一共有N个坑，n=3这种情况只占了3个坑
int n;
int path[N];//存一下全排列的路径，即每个坑里面是什么数字
bool flag[N]; //某个数用过没

void dfs(int u)
{
    if (u==n+1) //n个数就是n个位置，对位置里面填数进行遍历，把数填到了位置n就把一种情况枚举完了，这里不能写n，因为n位置还没赋值，是到了n+1个位置了，说明前n个位置遍历完了
    {
        for (int i=1;i<=n;i++)
        {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    else 
    {
        for (int i=1;i<=n;i++)
        {
            if (flag[i]==false) //如果这个数字没用过就把这个数字填到传进来的这个位置上，这句话是后写的，先写的里面的内容，发现逻辑上有问题需要先判断数字有没有用过，再把这个数字填上，所以加了一个判断
            {
                path[u] = i; //比如第1个位置先放上1
                flag[i] = true; //那么数字1就用过了
                dfs(u + 1);//对下一个位置再遍历，比如到了第2个位置，这句话走完，因为是一个递归的过程，出口在上面的if(u==n+1)的 时候，所以这时候就已经枚举完一种情况了，所以要回复现场
                path[u] = 0; //没进来的时候什么样，恢复完什么样
                flag[i] = false;
            }
        }
    }
}

//对位置进行深度遍历
int main()
{
    cin >> n; //1-n 做全排列
    dfs(1); //先填第一个位置上的数，对第一个位置进行深度遍历，这里要是写1的话，这个path就0号位置不要了

    return 0;
}

#include<iostream>
using namespace std;

//思路就是对位置进行深度搜索
const int N = 10;
int path[N];
int n;
bool flag[N]; //10个数字是否被用过的标记

void dfs(int p)
{
    if(p==n+1) 
    {
        for(int i=1;i<=n;i++) cout << path[i] <<" ";
        cout<<endl;
    }

    for (int i = 1; i <= n; i++)
    {
        if(flag[i]==false)
        {
            path[p] = i;
            flag[i] = true;
            dfs(p+1);
            path[p] = 0;
            flag[i] = false;
        }
    }
}s

int main()
{
    cin >> n; //对1-n进行全排列
    dfs(1); //从第1个位置开始深度遍历    
    return 0;
}