求解组合问题的一个迭代算法

参考资料：http://blog.csdn.net/sharpdew/article/details/755074

实际上这个算法的思路就是如下，举例说明比较直观一些，比如说计算{1,2,3,4,5}的3位组合

搜索过程如下

　　以order数组的内容为例，order[1]就指向a[0]，order[2]指向a[1]以此类推

　　order是一个数组，用来存放组合数在a[]中下标，order[0]作为一个flag来控制迭代循环何时结束，order[i]表示a[i-1]，通过修改order的内容来寻找组合，实际上跟直接找a[i]的组合是一样的

　　下划线表示回溯，黑体表示新的值，不符合要求的搜索结果用<strike></strike>划掉，因为a的下标最大就是4，所以当order的某个值为4的时候，就可以回溯了：

012,013,014,01_,02_,022,023,024,02_,03_,033,034,03_,04_,044,04_,0__,1__,11_,12_,122,123,124,12_,13_,133,134,13_,14_,144,14_,1__,2__,22_,23_,233,234,23_,24_,244,24_,2__,3__,33_,34_,3__,4__,___

#include "stdafx.h"

int combine(int a[], int n, int m)
{
    m = m > n ? n : m; // let's say m == 10, n == 9, so C(9, 10) is not correct, we compute C(9, 9)

    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 (int i = 1; i <= m; i++)
                std::cout << a[order[i]] << " ";
            std::cout << std::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;
    order = NULL;
    return count;
}

int main() {
    int a[] {1, 2, 3, 4, 5};
    combine(a, 5, 3);
    system("pause");
    return 0;
}