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 .
Example:
Input: [4, 6, 7, 7] Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
- The length of the given array will not exceed 15.
- The range of integer in the given array is [-100,100].
- The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
这道题让我们找出所有的递增子序列，那么我们应该不难想到，这题肯定是要先找出所有的子序列，从中找出递增的。找出所有的子序列的题我们之前也接触过Subsets和Subsets II，那两题不同之处在于数组中有没有重复项。而这道题明显是有重复项的，所以需要用到Subsets II中的解法。我们首先来看一种迭代的解法，对于重复项的处理，最偷懒的方法是使用set，利用其自动去处重复项的机制，然后最后返回时再转回vector即可。由于是找递增序列，所以我们需要对递归函数做一些修改，首先题目中说明了递归序列数字至少两个，所以只有当当前子序列个数大于等于2时，才加入结果。然后就是要递增，如果之前的数字大于当前的数字，那么跳过这种情况，继续循环，参见代码如下：
解法一：
class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { set<vector<int>> res; vector<int> out; helper(nums, 0, out, res); return vector<vector<int>>(res.begin(), res.end()); } void helper(vector<int>& nums, int start, vector<int>& out, set<vector<int>>& res) { if (out.size() >= 2) res.insert(out); for (int i = start; i < nums.size(); ++i) { if (!out.empty() && out.back() > nums[i]) continue; out.push_back(nums[i]); helper(nums, i + 1, out, res); out.pop_back(); } } };
我们也可以在递归中进行去重复处理，方法是用一个set保存中间过程的数字，如果当前的数字在之前出现过了，就直接跳过这种情况即可，参见代码如下：
解法二：
class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { vector<vector<int>> res; vector<int> out; helper(nums, 0, out, res); return res; } void helper(vector<int>& nums, int start, vector<int>& out, vector<vector<int>>& res) { if (out.size() >= 2) res.push_back(out); unordered_set<int> st; for (int i = start; i < nums.size(); ++i) { if (!out.empty() && out.back() > nums[i] || st.count(nums[i])) continue; out.push_back(nums[i]); st.insert(nums[i]); helper(nums, i + 1, out, res); out.pop_back(); } } };
下面我们来看迭代的解法，还是老套路，先看偷懒的方法，用set来去处重复。对于递归的处理方法跟之前相同，参见代码如下：
解法三：
class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> cur(1); for (int i = 0; i < nums.size(); ++i) { int n = cur.size(); for (int j = 0; j < n; ++j) { if (!cur[j].empty() && cur[j].back() > nums[i]) continue; cur.push_back(cur[j]); cur.back().push_back(nums[i]); if (cur.back().size() >= 2) res.insert(cur.back()); } } return vector<vector<int>>(res.begin(), res.end()); } };
我们来看不用set的方法，使用一个哈希表来建立每个数字对应的遍历起始位置，默认都是0，然后在遍历的时候先取出原有值当作遍历起始点，然后更新为当前位置，如果某个数字之前出现过，那么取出的原有值就不是0，而是之前那个数的出现位置，这样就就不会产生重复了，如果不太好理解的话就带个简单的实例去试试吧，参见代码如下：
解法四：
class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { vector<vector<int>> res, cur(1); unordered_map<int, int> m; for (int i = 0; i < nums.size(); ++i) { int n = cur.size(); int start = m[nums[i]]; m[nums[i]] = n; for (int j = start; j < n; ++j) { if (!cur[j].empty() && cur[j].back() > nums[i]) continue; cur.push_back(cur[j]); cur.back().push_back(nums[i]); if (cur.back().size() >= 2) res.push_back(cur.back()); } } return res; } };
本文转自博客园Grandyang的博客，原文链接：Increasing Subsequences 递增子序列，如需转载请自行联系原博主。
