全排列问题

#include<bits/stdc++.h>
using namespace std;
int n,pd[100],used[100];//pd是判断是否用过这个数
void print()//输出函数
{
    int i;
    for(i=1;i<=n;i++)
    printf("%5d",used[i]);//保留五位常宽
    cout<<endl;
}
void dfs(int k)//深搜函数，当前是第k格
{
    int i;
    if(k==n) //填满了的时候
    {
        print();//输出当前解
        return;
    }
    for(i=1;i<=n;i++)//1-n循环填数
    {
        if(!pd[i])//如果当前数没有用过
        {
            pd[i]=1;//标记一下
            used[k+1]=i;//把这个数填入数组
            dfs(k+1);//填下一个
            pd[i]=0;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);//注意，这里是从第0格开始的！
    return 0;
}

这种代码的时间复杂度是多少，个人觉得是$O(n!)$

但是又有人说这是$O(2^n)$的算法

后来自己推了一下递推式好像真是$O(2^n)$

但是直观上这个dfs可以看成有n个for套在一起最外面的循环n次第二个循环n-1次……

这样不就是$O(n!)$

问题出在哪

求一个$O(n!)$的代码或者题目

如果蒟蒻有错误请各位神犇指正