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 中的解法。首先来看一种迭代的解法，对于重复项的处理，最偷懒的方法是使用 TreeSet，利用其自动去处重复项的机制，然后最后返回时再转回 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();
}
}
};
我们也可以在递归中进行去重复处理，方法是用一个 HashSet 保存中间过程的数字，如果当前的数字在之前出现过了，就直接跳过这种情况即可，参见代码如下：
解法二：
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();
}
}
};
下面我们来看迭代的解法，还是老套路，先看偷懒的方法，用 TreeSet 来去处重复。对于递归的处理方法跟之前相同，参见代码如下：
解法三：
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());
}
};
我们来看不用 TreeSet 的方法，使用一个 HashMap 来建立每个数字对应的遍历起始位置，默认都是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(), 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;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/491
类似题目：
参考资料：
https://leetcode.com/problems/increasing-subsequences/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
