leetcode -- Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.

Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

思路

$T = a_1 + a_2 +...+a_k$，首先固定某1个元素$a_i(1 le i le k)$,则剩余元素相加等于$T-a_i$.而剩余元素相加可以以下递归vector<vector<int> > pre = combinationSum(c, target - *i)。其中的1个目的是为了快速减小$target$（以致$target = a_1$乃至$target）.</p> <div class="w_dama2"><code class="language-C++ hljs cpp"><span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> &gt;</span> combinationSum(<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> &amp;candidates, <span class="hljs-keyword">int</span> target) { <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> &gt;</span> ret; <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span>::iterator i, cbeg = candidates.begin(), cend = candidates.end(); sort(cbeg, cend); <span class="hljs-keyword">for</span>(i = cbeg; i &lt; cend; i++){ <span class="hljs-keyword">if</span>(*i == target){ <span class="hljs-comment">//既是递归出口也是1种case</span> <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> tmp(<span class="hljs-number">1</span>, *i); ret.push_back(tmp); } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(*i &lt; target){ <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> c(i, cend); <span class="hljs-comment">//先肯定1个元素*i,再进行递归，将target逐渐变小</span> <span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> &gt;</span> pre = combinationSum(c, target - *i); <span class="hljs-keyword">if</span>(!pre.empty()){ <span class="hljs-comment">//如果非空，则将*i元素添加至各个组合中</span> <span class="hljs-keyword">for</span>(<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-stl_container"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;</span> &gt;</span>::iterator vec = pre.begin(); vec &lt; pre.end(); vec++){ (*vec).push_back(*i); sort((*vec).begin(), (*vec).end()); } <span class="hljs-comment">//将某1固定*i元素下，所有符合要求的组合添加至终究结果</span> ret.insert(ret.end(), pre.begin(), pre.end()); } } <span class="hljs-keyword">else</span> <span class="hljs-keyword">break</span>; } <span class="hljs-keyword">return</span> ret; } };</code></div></div> <script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split(' ').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); });$