<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> * [Upper Folder - 上一級目錄](../) * [Source Code - 源碼](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/DuplicableCombination.hpp) * [Test Code - 測試](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/DuplicableCombination.cpp) -------- ### Duplicable Combination ### （元素）重復的組合 <div> 問題： <p id="i">在有\(n\)個互不相同元素的集合\(A = \{a_0,a_1,a_2, \dots ,a_{n-1} \}\)中，任意取\(m\)個元素（\(m \leq n\)，\(m\)和\(n\)都是自然數，并且同一個元素可以重復使用）的所有組合。例如對于集合\(A = \{1, 2, 3\}\)，從中取出\(3\)個元素可重復的所有組合為：</p> \[ [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] \] 解法： <p id="i"><a href="https://zhaochenyou.github.io/Way-to-Algorithm/Search/Recursion">Recursion</a>可以解決這個問題。所求的組合是長度為\(m\)的數組\(S\)，其中每個元素\(i\)可以選擇的值為集合\(A\)中的任意一個元素。因此我們只需要遞歸的對每個元素i選擇一個值，然后遞歸下去對元素i+1設置一個值，直到將數組中所有元素都選擇了一個值，即可得到一個組合。 </p> <p id="i">所求組合的長度為\(m\)，集合\(A\)的成員有\(n\)個，該算法的時間復雜度\(O(m^n)\)。 </p> </div> Online Judge: * [leetcode-40](https://leetcode.com/problems/combination-sum/) * [leetcode-40 source.hpp](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/attachment/leetcode-40.hpp)