dfs全排列

题意  盒子放牌（n=3) --> 按照 1 2 3 的顺序  走到第四个盒子时,手中已经没有牌了

解法  当下如何做和下一步如何做相同,写成递归  如果走不通了就回溯换路

时间复杂度 第一个盒子->手中有n张牌,每张牌都要放入盒子中,O(n)
           第二个盒子-> 手中有n-1张牌,每张牌都会放入第二个盒子中,O(n-1)
           n-2 n-3 ...1
           
           O(n*(n-1)*(n-2)...*2*1)==O(n!) 递归形式的n个for循环,即是乘法

//代码非原创,源自某牛学长~

#include
#include
using namespace std;
const int N=2e5+10;
bool vis[N];
int box[N];
int n;
void dfs(int step)
{
    if(step==n+1)//n+1号盒子
    {
        for(int i=1; i<=n; i++)
        {
            i==1||printf(" ");  //短路 -> 第一句是真 就不判断第二句话
            printf("%d",box[i]);// 1 2 3 4 先输出1 然后空格数字 空格数字... 
        }
        printf("n");
        return ;//没有return会产生无限递归
    }
    for(int i=1; i<=n; i++)
    {
        if(!vis[i])//i号牌在手里
        {
            box[step]=i;//把i号牌放到第step个盒子中
            vis[i]=1;//标记第i号牌已经不在手里了
            dfs(step+1);//递归到下一个盒子
            vis[i]=0;//递归返回后取回盒子里的牌放回手中,进行下一次尝试-->回溯
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
        {
            memset(vis,0,sizeof vis);
            dfs(1);
        }
        
    return 0;
}

 c++的stl中有现成的全排列函数 next_permutation();