该题其实在leetcode上有原题，好几道都是关于全排列的

算法1

借助visited数组标记某个数是否被使用过，空间复杂度相对较高

C++ 代码

//类似于leetcode全排列

#include<iostream>
using namespace std;
#include<bits/stdc++.h>

int n;
vector<int> temp;
bool visited[10];

void dfs(int num)
{
    if(num==n+1)
    {
       // sort(temp.begin(),temp.end());
        for(int i=0;i<n;i++)
        {
            cout<<temp[i]<<" ";
        }
        cout<<endl;
    }
    else{
        for(int i=1;i<=n;i++)
        {
            if(!visited[i])
            {
                visited[i]=true;
                temp.push_back(i);
                dfs(num+1);
                visited[i]=false;
                temp.pop_back();
            }
        }
    }
}

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

算法2

参考闫大佬的思想,因为这里涉及到某个数是否被使用过的问题，所以可以很自然的想到用位运算(二进制数)表示是否用过,这样的话，用一个整数来代替visited数组，可以大大减少空间复杂度

C++ 代码

//类似于leetcode全排列

#include<iostream>
using namespace std;
#include<bits/stdc++.h>

int n;
vector<int> temp;
//bool visited[10];

void dfs(int num,int state)
{
    if(num==n+1)
    {
       // sort(temp.begin(),temp.end());
        for(int i=0;i<n;i++)
        {
            cout<<temp[i]<<" ";
        }
        cout<<endl;
    }
    else{
        for(int i=0;i<n;i++)
        {
            if(!((state>>i)&1))
            {
               state|=1<<i;
               temp.push_back(i+1);
               dfs(num+1,state);
               state=state-(1<<i);
               temp.pop_back();
            }
        }
    }
}

int main()
{
    cin>>n;
    //初始化时，所有的数都没有被用过，所以是0
    dfs(1,0);
    return 0;
}