您當前位置：首頁 > php開源 > php教程 > leetcode -- Combination Sum

leetcode -- Combination Sum

來源：程序員人生發布時間：2015-03-23 08:34:17 閱讀次數：2693次

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）. <div id="mwsqua40mo" class="w_dama2"><code class="language-C++ hljs cpp">class Solution { public: vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > ret; vector<int>::iterator i, cbeg = candidates.begin(), cend = candidates.end(); sort(cbeg, cend); for(i = cbeg; i < cend; i++){ if(*i == target){ //既是遞歸出口也是1種case vector<int> tmp(1, *i); ret.push_back(tmp); } else if(*i < target){ vector<int> c(i, cend); //先肯定1個元素*i,再進行遞歸，將target逐漸變小 vector<vector<int> > pre = combinationSum(c, target - *i); if(!pre.empty()){ //如果非空，則將*i元素添加至各個組合中 for(vector<vector<int> >::iterator vec = pre.begin(); vec < pre.end(); vec++){ (*vec).push_back(*i); sort((*vec).begin(), (*vec).end()); } //將某1固定*i元素下，所有符合要求的組合添加至終究結果 ret.insert(ret.end(), pre.begin(), pre.end()); } } else break; } return 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); }); });$