递归实现排列型枚举

先画出递归树：

第一次写的错误代码：

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int>res;
bool st[10];

void Print()
{
    for(auto& e:res)
    {
        printf("%d ",e);
    }
    puts("");
}

void dfs(int num)
{
    if(num==n+1)
    {
        Print();
        return;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            res.push_back(i);
            st[i]=true;
            dfs(i+1);
            res.pop_back();
            st[i]=false;
        }        
    }
}

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

结果并不是全排列，因为从递归树中可以看出，得到结果的是最后一行节点，这些节点的结尾的值并不是都是n+1。

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int>res;
bool st[10];

void Print()
{
    for(auto& e:res)
    {
        printf("%d ",e);
    }
    puts("");
}

void dfs(int num)
{
    if(num==n+1)
    {
        Print();
        return;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            res.push_back(i);
            st[i]=true;
            dfs(i+1);
            res.pop_back();
            st[i]=false;
        }        
    }
}

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