Chapter-7 CombinatorialMathematics 第7章 组合数学 - DuplicableCombination （元素）可重复的组合

• Source Code - 源码
• Test Code - 测试

---

Duplicable Combination

（元素）重复的组合

问题：

在有(n)个互不相同元素的集合(A = {a0,a_1,a_2, \cdots ,a{n-1} })中，任意取(m)个元素（(m \leq n)，(m)和(n)都是自然数，并且同一个元素可以重复使用）的所有组合。例如对于集合(A = {1, 2, 3})，从中取出(3)个元素可重复的所有组合为：

[
[1, 1, 1] \
[1, 1, 2] \
[1, 2, 1] \
[2, 1, 1] \
[1, 2, 2] \
[2, 1, 2] \
[2, 2, 1] \
[2, 2, 2] \
[2, 2, 3] \
[2, 3, 2] \
[3, 2, 2] \
[2, 3, 3] \
[3, 2, 3] \
[3, 3, 2] \
[3, 3, 3] \
[1, 1, 3] \
[1, 3, 1] \
[3, 1, 1] \
[1, 3, 3] \
[3, 1, 3] \
[3, 3, 1] \
[1, 2, 3] \
[1, 3, 2] \
[3, 2, 1] \
[3, 1, 2] \
[2, 1, 3] \
[2, 3, 1]
]
解法：

Recursion可以解决这个问题。所求的组合是长度为(m)的数组(S)，其中每个元素(i)可以选择的值为集合(A)中的任意一个元素。因此我们只需要递归的对每个元素i选择一个值，然后递归下去对元素i+1设置一个值，直到将数组中所有元素都选择了一个值，即可得到一个组合。

所求组合的长度为(m)，集合(A)的成员有(n)个，该算法的时间复杂度(O(m^n))。

Online Judge:

• leetcode-40
• leetcode-40 source.hpp