盡管排列組合是生活中經常遇到的問題，可在程序設計時，不深入思考或者經驗不足都讓人無從下手。由于排列組合問題總是先取組合再排列，并且單純的排列問題相對簡單，所以本文僅對組合問題的實現進行詳細討論。以在n個數中選取m(0<m<=n)個數為例，問題可分解為：
1. 首先從n個數中選取編號最大的數，然后在剩下的n-1個數里面選取m-1個數，直到從n-(m-1)個數中選取1個數為止。
2. 從n個數中選取編號次小的一個數，繼續執行1步，直到當前可選編號最大的數為m。
很明顯，上述方法是一個遞歸的過程，也就是說用遞歸的方法可以很干凈利索地求得所有組合。
下面是遞歸方法的實現：
下面是非遞歸的回溯方法的實現：
int* order = new int[m+1];
for(int i=0; i<=m; i++)
order[i] = i-1; // 注意這里order[0]=-1用來作為循環判斷標識
int count = 0;
int k = m;
bool flag = true; // 標志找到一個有效組合
while(order[0] == -1)
{
if(flag) // 輸出符合要求的組合
{
for(i=1; i<=m; i++)
cout << a[order[i]] << " ";
cout << endl;
count++;
flag = false;
}
order[k]++; // 在當前位置選擇新的數字
if(order[k] == n) // 當前位置已無數字可選，回溯
{
order[k--] = 0;
continue;
}
if(k < m) // 更新當前位置的下一位置的數字
{
order[++k] = order[k-1];
continue;
}
if(k == m)
flag = true;
}
delete[] order;
return count;
}
// 回溯方法
cout << combine(a,N,3) << endl;
// 遞歸方法
int b[M];
combine(a,N,M,b,M);
return 0;
}
n個數的全排列問題相對簡單，可以通過交換位置按序枚舉來實現。STL提供了求某個序列下一個排列的算法next_permutation，其算法原理如下：
1. 從當前序列最尾端開始往前尋找兩個相鄰元素，令前面一個元素為*i，后一個元素為*ii，且滿足*i<*ii；
2. 再次從當前序列末端開始向前掃描，找出第一個大于*i的元素，令為*j（j可能等于ii），將i，j元素對調；
3. 將ii之后（含ii）的所有元素顛倒次序，這樣所得的排列即為當前序列的下一個排列。
其實現代碼如下：