可重复组合问题是指，在计算（生成）组合时可以允许元素重复的一类组合问题。例如，对于有四个元素的集合{a, b, c, d}，其可重复组合C(4, 3）有20个：aaa, aab, aac, aad, abb, abc, abd, acc, acd, add, bbb, bbc, bbd, bcc, bcd, bdd, ccc, ccd, cdd, ddd。

用C(n, k)表示从n个元素中选出k个元素（允许重复）的组合问题，那么此问题可以分解为两个子问题：
C(n, k-1) - 包含第n个元素，选择另外k-1个进行组合
C(n-1, k) - 不包含第n个元素，对另外k个进行组合

推理如下：
C(n, k)中n个元素的所有k元素组合可以分成两部分。
第一部分的每个组合均以第一个元素开始，再连接上k-1个元素的组合，即再连接上C(n,k-1)的每一个组合；
第二部分的每个组合不含有第一个元素，即C(n-1, k)中的每一个组合（此时元素为后n-1个元素）。

因此，C(n, k)分解为C(n, k-1)和C(n-1, k)。

如果用f(n, k)表示C(n, k)中的组合数，那么有：
（1）当k = 1时，f(n, k) = n
（2）当n = 1时，f(n, k) = 1
（3）当k > 1且n > 1时，f(n, k) = f(n, k -1) + f(n-1, k)

此外，有公式f(n, k) = C(n + k -1, k)（表示n+k-1选k的组合数，没有重复元素）

这样，我们就可以根据这个递推关系构造递归实现了。

unsigned int combinational(int n, int k)
{
    if(k==1)
        return(n);

    if(n==1)
        return(1);

    if(k>1 && n>1)
        return combinational(n, k-1) + combinational(n-1, k);

    return 0;
}

这个问题是一个典型的NP完全性问题，我们自然会想到用backtracing去遍历生成每一个可能组合，但是，是不是用dynamic programming去做的话效率更高呢？我们来看看这个问题符不符合使用dynamic programming的条件：
1. 子问题重叠。可以看出在遍历计算过程中会出现很多相同的f(n, k)，比如计算f(6,3)会先计算f(6, 2)和f(5, 3)，而计算f(7, 2)的时候也会计算f(6,2)。
2. 备忘录。显然，备忘录能极大地减少这个问题的计算量，我们可以将这个NP问题的复杂度降为N*K。


unsigned int dpcombinational(int n, int k)
{
    int* a = new int[n*k];
    memset(a, 0, n*k*sizeof(int));
    int ret = 0;

    //if selection count is 1, set the initial number to 1..n
    for(int i=0; i<n; i++)
        a[i*k] = i+1;

    //if total number of the set is 1, set the initial number to 1
    for(int i=1; i<k; i++)
        a[i] = 1;

    //recursion solution
    for(int i=1; i<n; i++)
        for(int j=1; j<k; j++)
            a[i*k + j] = a[i*k + (j-1)] + a[(i-1)*k + j];

    ret = a[n*k-1];

    delete[] a;
    return ret;
}