{"id":2218,"date":"2016-09-26T14:22:09","date_gmt":"2016-09-26T06:22:09","guid":{"rendered":"http:\/\/boweihe.me\/?p=2218"},"modified":"2016-09-26T14:22:09","modified_gmt":"2016-09-26T06:22:09","slug":"leetcode-40-combination-sum-ii","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2218","title":{"rendered":"LeetCode 40. Combination Sum II"},"content":{"rendered":"<h3>\u601d\u8def<\/h3>\n<p>\u9012\u5f52\uff1f\u5475\u5475<br \/>\n\u9700\u8981\u5224\u65ad\u4e24\u4e2a\u89e3\u662f\u5426\u76f8\u7b49\uff0c\u76ee\u524d\u6ca1\u6709\u4ec0\u4e48\u597d\u529e\u6cd5\uff0c\u4eceboost\u5e93\u91cc\u6284\u4e86\u4e2ahash\u51fd\u6570\u8fc7\u6765\u3002<\/p>\n<h3>\u4ee3\u7801<\/h3>\n<pre class=\"lang:c++ decode:true \">class Solution {\nprivate:\n\tvector&lt;vector&lt;int&gt;&gt; results;\n\tsize_t hashOfIntVec(const vector&lt;int&gt;&amp; vec) const {\n\t\tsize_t seed = vec.size();\n\t\tfor (auto&amp; i : vec) {\n\t\t\tseed ^= i + 0x9e3779b9 + (seed &lt;&lt; 6) + (seed &gt;&gt; 2);\n\t\t}\n\t\treturn seed;\n\t}\npublic:\n\tvoid subCombSum(vector&lt;int&gt;&amp; candidates, int start, int target, vector&lt;int&gt;&amp; path) {\n\t\tfor (int i = start; i&lt;candidates.size(); i++) {\n\t\t\tif (target - candidates[i] == 0) {\n\t\t\t\t\/\/bingo!\n\t\t\t\tpath.push_back(candidates[i]);\n\t\t\t\tvector&lt;int&gt; pathCopy(path);\n\t\t\t\tsort(pathCopy.begin(), pathCopy.end());\n\t\t\t\tsize_t hashVal = hashOfIntVec(pathCopy);\n\t\t\t\tbool hasSame = false;\n\t\t\t\tfor (int j = 0; j &lt; results.size(); j++) {\n\t\t\t\t\tif (hashVal == hashOfIntVec(results[j])) {\n\t\t\t\t\t\thasSame = true;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tif(!hasSame)\n\t\t\t\t\tresults.push_back(pathCopy);\n\t\t\t\tpath.erase(path.end() - 1);\n\t\t\t}\n\t\t\telse if (target - candidates[i] &gt; 0) {\n\t\t\t\tpath.push_back(candidates[i]);\n\t\t\t\tsubCombSum(candidates, i + 1, target - candidates[i], path);\n\t\t\t\tpath.erase(path.end() - 1);\n\t\t\t}\n\t\t}\n\t}\n\tvector&lt;vector&lt;int&gt;&gt; combinationSum2(vector&lt;int&gt;&amp; candidates, int target) {\n\t    vector&lt;int&gt; path;\n\t\tsubCombSum(candidates, 0, target, path);\n\t\treturn results;\n\t}\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u601d\u8def \u9012\u5f52\uff1f\u5475\u5475 \u9700\u8981\u5224\u65ad\u4e24\u4e2a\u89e3\u662f\u5426\u76f8\u7b49\uff0c\u76ee\u524d\u6ca1\u6709\u4ec0\u4e48\u597d\u529e\u6cd5\uff0c\u4eceboost\u5e93\u91cc\u6284\u4e86\u4e2ahash\u51fd\u6570\u8fc7\u6765\u3002 \u4ee3\u7801 class Solution { private: vector&lt;vector&lt;int&gt;&gt; results; size_t hashOfIntVec(const vector&lt;int&gt;&amp; vec) const { size_t seed = vec.size(); for (auto&amp; i : vec) { seed ^= i + 0x9e3779b9 + (seed &lt;&lt; 6) + (seed &gt;&gt; 2); } return seed; } public: void subCombSum(vector&lt;int&gt;&amp; candidates, int start, int target, vector&lt;int&gt;&amp; path) { for [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-2218","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2218","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2218"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2218\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}