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); }); });$

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!