一道面试题（算法）

一道面试题（算法）打印一整数N的正整数组合（递减）如3有2 1或1 1 1两种组合；upunsigned char a[100] = {0};bool fill(int j,int N){for(int i=j;i<N; i)if((a[j-1]>a[i] 1)){--a[j-1]; a[i];return true;}return false;}int main(int argc, char* argv[]){int M = 3;for(int N=1;N<=M;N ){memset(a,1,N);a[0] = M-N;int k = 1;while(k){for(int i=0;i<N; i)printf("]",a[i]);//show();printf("");while(!fill(k,N))if(--k<1)break;if(k>=1) k;}}}typedef struct{ int curPos; int buf[1];}Data;typedef struct _link{ _link *next; int count; int buf[1];}Link;Link * head = NULL;Link * NewLink(int count, int *buf){ Link * link = (Link *)malloc((count 1) * sizeof(int) sizeof(Link *)); link->count = count; memcpy(link->buf, buf, sizeof(int)*count); link->next = NULL; return link;}void Sort(int *buf, int len){ for(int i = 0; i < len - 1; i ) { for(int j = len - 1; j > i; j--) { if(buf[i] < buf[j]) { int temp = buf[i]; buf[i] = buf[j]; buf[j] = temp; } } }}void getSub(unsigned int val, Data *data){ bool Catched = false; if( val == 1 ) { data->buf[data->curPos] = 1; data->curPos ; Catched = true; } else if( !val ) { Catched = true; } if( Catched ) { Link *curlink = head; Link * link = NewLink(data->curPos, data->buf); Sort(link->buf, link->count); while( curlink ) { if( curlink->count == link->count ) { if( !memcmp(curlink->buf, link->buf, link->count) ) break; } curlink = curlink->next; } if( !curlink ) { if( !head ) { head = link; } else { curlink = head; while( curlink->next ) { curlink = curlink->next; } curlink->next = link; } cout << "一个组合:"; for(int i = 0; i < data->curPos; i ) { cout << data->buf[i] << "\t"; } } } else { int curpos = data->curPos; for(int n = val; n > 0 ; n--) { data->curPos = curpos; data->buf[curpos] = n; data->curPos ; getSub(val - n, data); } }}int main(int argc, char* argv[]){ unsigned int value = 1; while( value ) { cout << "输入一个正整数："; cin >> value; Data *data = (Data *)malloc( (value 1) * sizeof(int) ); data->curPos = 0; getSub(value, data); cout << endl; Link * nextlink; while( head ) { nextlink = head->next; free( head ); head = nextlink; } free( data ); }}上面的排除了相同的组合.高程的辅导书里就有这么一道o