{"id":3207,"date":"2018-07-17T21:19:36","date_gmt":"2018-07-18T04:19:36","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3207"},"modified":"2018-09-14T08:40:02","modified_gmt":"2018-09-14T15:40:02","slug":"leetcode-491-increasing-subsequences","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-491-increasing-subsequences\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 491. Increasing Subsequences"},"content":{"rendered":"
\n
\n

Problem<\/strong><\/h2>\n

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .<\/p>\n

Example:<\/b><\/p>\n

Input:<\/b> [4, 6, 7, 7]\r\nOutput:<\/b> [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The length of the given array will not exceed 15.<\/li>\n
  2. The range of integer in the given array is [-100,100].<\/li>\n
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n
    Solution: DFS<\/strong><\/h1>\n
    Time complexity: O(2^n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 140 ms (<99.88%)\r\nclass Solution {\r\npublic:\r\n  vector<vector<int>> findSubsequences(vector<int>& nums) {\r\n    vector<vector<int>> ans;\r\n    vector<int> cur;\r\n    dfs(nums, 0, cur, ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(const vector<int>& nums, int s, vector<int>& cur, vector<vector<int>>& ans) {    \r\n    unordered_set<int> seen;\r\n    for (int i = s; i < nums.size(); ++i) {\r\n      if (!cur.empty() && nums[i] < cur.back()) continue;\r\n      \/\/ each number can be used only once at the same depth.\r\n      if (seen.count(nums[i])) continue; \r\n      seen.insert(nums[i]);\r\n      cur.push_back(nums[i]);\r\n      if (cur.size() > 1) \r\n        ans.push_back(cur);\r\n      dfs(nums, i + 1, cur, ans);\r\n      cur.pop_back();\r\n    }\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an…<\/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,305,177,229],"class_list":["post-3207","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-dfs","tag-increasing","tag-medium","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3207","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=3207"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3207\/revisions"}],"predecessor-version":[{"id":3967,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3207\/revisions\/3967"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}