題目地址：  http://acm.hdu.edu.cn/showPRoblem.php?pid=2062

/************************************************************************

本想用深搜（dfs），不過(guò)超時(shí)了。。無(wú)奈絞盡腦汁，用了種無(wú)奈的方法。

/********************

把他的子集畫(huà)成一個(gè)多叉樹(shù)的圖，假設(shè)圖中紅線圈起來(lái)的這一路就是答案，如果用遍歷樹(shù)的方法找到這個(gè)答案，必定超時(shí)。

那么就及早的剪枝，不符合條件的答案，直接不往下探索了，

/*********************

其實(shí)每一個(gè)結(jié)點(diǎn)就代表一個(gè)子集，子集就是答案。上圖假設(shè)紅色圓圈的結(jié)點(diǎn)就是答案，答案就是這一整條路連起來(lái)的數(shù)字。

每往下走一個(gè)結(jié)點(diǎn)，都篩選出正確的唯一一條分支。

/****************************************************************

代碼如下：

/********************

#include<stdio.h>#include<algorithm>using namespace std;long long c[21]={0,1},j,n; //j用來(lái)統(tǒng)計(jì)當(dāng)前走到哪里了int m;void swap(int &a,int &b)//c++中的引用，實(shí)現(xiàn)值得交換{    int temp=a;    a=b;    b=temp;}void po(int a[],int begen){    if(j>=n||begen>m)    {        printf("%d",a[1]);        for(int i=2;i<begen;i++)            printf(" %d",a[i]);        puts("");        return;    }    long long t=j;//用t暫時(shí)記錄下j    for(int i=begen;i<=m;i++)    {        if(i-begen+1==(n-t-1)/(c[m-begen]+1)+1)//判斷條件很復(fù)雜,意思是檢索到有答案的那一個(gè)分支時(shí)，就執(zhí)行下面        {            j++;   //printf("樹(shù)的路徑:**%3d ** i:%3d,begen:%3d** /n",i-begen+1,i,begen);            swap(a[i],a[begen]);        //選擇a[i]這個(gè)數(shù)字，把它交換到第begen的位置            sort(a+begen+1,a+m+1);    //對(duì)剩下的數(shù)字排序（字典序，從小到大）            po(a,begen+1);      //遞歸，尋找下一個(gè)數(shù)字，排到（數(shù)組a中）begen+1的位置            break;//以后的路都不符合了，直接break；        }        else            j+=c[m-begen]+1;//統(tǒng)計(jì)走到第多少個(gè)子集了    }}int main(){    int a[21]={0,1};    for(long long i=2;i<=20;i++)        c[i]=i*(c[i-1]+1);    while(~scanf("%d%lld",&m,&n))    {        for(int i=1;i<=m;i++)            a[i]=i;        j=0;        po(a,1);    }    return 0;}