{"id":5672,"date":"2019-09-30T23:37:48","date_gmt":"2019-10-01T06:37:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5672"},"modified":"2019-09-30T23:41:29","modified_gmt":"2019-10-01T06:41:29","slug":"leetcode-77-combinations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-77-combinations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 77. Combinations"},"content":{"rendered":"\n<p>Given two integers&nbsp;<em>n<\/em>&nbsp;and&nbsp;<em>k<\/em>, return all possible combinations of&nbsp;<em>k<\/em>&nbsp;numbers out of 1 &#8230;&nbsp;<em>n<\/em>.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong>&nbsp;n = 4, k = 2\n<strong>Output:<\/strong>\n[\n  [2,4],\n  [3,4],\n  [2,3],\n  [1,2],\n  [1,3],\n  [1,4],\n]<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(C(n, k))<br>Space complexity: O(k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> combine(int n, int k) {\n    vector<vector<int>> ans;\n    vector<int> cur;\n    function<void(int)> dfs = [&](int s) {\n      if (cur.size() == k) { \n        ans.push_back(cur); \n        return;\n      }\n      for (int i = s; i < n; ++i) {\n        cur.push_back(i + 1);\n        dfs(i + 1);\n        cur.pop_back();\n      }  \n    };\n    dfs(0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-78-subsets\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-78-subsets\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-90-subsets-ii\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-90-subsets-ii\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-39-combination-sum\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-39-combination-sum\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given two integers&nbsp;n&nbsp;and&nbsp;k, return all possible combinations of&nbsp;k&nbsp;numbers out of 1 &#8230;&nbsp;n. Example: Input:&nbsp;n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2],&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[122,33,177,42],"class_list":["post-5672","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-dfs","tag-medium","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5672","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5672"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5672\/revisions"}],"predecessor-version":[{"id":5676,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5672\/revisions\/5676"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5672"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5672"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5672"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}