给定n个不同的数，问这n个数可以组成多少个不同的序列且序列中相邻的元素之差大于一。
一开始我用递归进行全排列，然后逐个比较。后来看到最多有25个数，就知道肯定超时了（时间复杂度已经达到O（n！）了）。不知各位大牛有何建议？这肯定是有简便方法的，不过我就是没想出来。。。
附上我超时的代码：
#include<iostream>
using namespace std;
int fabs(int n)
{
    if(n<0)
        return -n;
    else
        return n;
}
int counter=0;
void Swap(int& a,int& b)
{
    int temp=a;
    a=b;
    b=temp;
}
void pai(int a[],int n,int k,int end)
{
    int flag=1;
    if(k==end)
    {
        //cout<<"yes.\n";
        /*for(int i=0;i<n-1;i++)
        {
            if((a[i]-a[i+1]==1)||(a[i]-a[i+1]==-1))
                return;
        }*/
        counter++;
        return;
        /*for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;*/
    }
    for(int i=k;i<n;i++)
    {
        Swap(a[k],a[i]);
        if(fabs(a[k]-a[k+1])>1)
        {
            if(k>=1)
            {
                if(fabs(a[k]-a[k-1])>1)
                    pai(a,n,k+1,end);
            }
            else
                pai(a,n,k+1,end);
        }
        
        //pai(a,n,k+1,end);
        Swap(a[k],a[i]);
    }
}

int main()
{
    int T,num;
    int a[26];
    cin>>T;
    while(T--)
    {
        counter=0;
        cin>>num;
        for(int i=0;i<num;i++)
            cin>>a[i];
        pai(a,num,0,num-1);
        cout<<counter<<endl;
        
    }
    return 0;
}

你可以去 C 版问问这个问题，那边参与讨论的人比较多。不过这个题也挺有意思，如果我有空没准也会想想。

问个问题，他说给定 n 个数。是这 n 个数就是 从1到n 这 n 个数吗？还是说它确实会给出 n 个数？

给出n个数。。

fabs  好熟悉的字母啊........