元素可重复组合算法

可重复组合问题是指，在计算（生成）组合时可以允许元素重复的一类组合问题。例如，对于有四个元素的集合{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);