{"id":5702,"date":"2019-10-02T09:28:32","date_gmt":"2019-10-02T16:28:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5702"},"modified":"2019-10-02T09:29:22","modified_gmt":"2019-10-02T16:29:22","slug":"leetcode-46-permutations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-46-permutations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 46. Permutations"},"content":{"rendered":"\n<p>Given a collection of&nbsp;<strong>distinct<\/strong>&nbsp;integers, return all possible permutations.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> [1,2,3]\n<strong>Output:<\/strong>\n[\n  [1,2,3],\n  [1,3,2],\n  [2,1,3],\n  [2,3,1],\n  [3,1,2],\n  [3,2,1]\n]<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n!)<br>Space complexity: O(n)<\/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>> permute(vector<int>& nums) {\n    const int n = nums.size();\n    vector<vector<int>> ans;\n    vector<int> used(n);\n    vector<int> path;\n    function<void(int)> dfs = [&](int d) {\n      if (d == n) {\n        ans.push_back(path);\n        return;\n      }\n      for (int i = 0; i < n; ++i) {\n        if (used[i]) continue;\n        used[i] = 1;\n        path.push_back(nums[i]);\n        dfs(d + 1);\n        path.pop_back();\n        used[i] = 0;\n      }\n    };\n    dfs(0);\n    return ans;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Related Problems<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-47-permutations-ii\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-47-permutations-ii\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given a collection of&nbsp;distinct&nbsp;integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] Solution: DFS Time complexity: O(n!)Space&#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":[33,177,376,121,42],"class_list":["post-5702","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-medium","tag-on","tag-permutation","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5702","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=5702"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5702\/revisions"}],"predecessor-version":[{"id":5704,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5702\/revisions\/5704"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}