m個數中取n個數的所有組合問題
從左到右掃描數組元素值的“10”組合,找到第一個“10”組合後將其變為“01”組合,同時將其左邊的所有“1”全部移動到數組的最左端
代碼如下:
#includeusing namespace std; #define SIZE 100 struct data{ int elem; int b; }; inline void move(data tmp[], int num, int r){ for(int i = 0; i < num; i++){ tmp[i].b = 1; } for(int j = num; j < r; j++){ tmp[j].b = 0; } } inline void println(data tmp[], int len){ for(int i = 0; i < len; i++){ if(tmp[i].b == 1) cout << tmp[i].elem << " "; } cout << endl; } void comb(int arr[], int len, int count){ data tmp[SIZE]; for(int i = 0; i < len; i++){ tmp[i].elem = arr[i]; if(i < count){ tmp[i].b = 1; } else{ tmp[i].b = 0; } } println(tmp, len); while(true){ int j = 0; int num = 0; while(j+1 < len){ if(tmp[j].b == 1){ num++; if(tmp[j+1].b == 0){ tmp[j].b = 0; tmp[j+1].b = 1; move(tmp, num-1, j); break; } } ++j; } if(j+1 < len) println(tmp, len); else break; } } int main(int argc, char* argv[]) { int testArr[] = {2, 5, 1, 7, 4}; int len = sizeof(testArr)/sizeof(int); comb(testArr, len, 3); return 0; }