LeetCode Increasing Subsequences 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:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

---

给定一个数组，求出改数组的所有递增子序列。注意两点，一是递增，二是子序列。 因为是求子序列，所以没必要对数组排序！ 使用DFS，尝试将每个数加入cand，然后从下一个数开始，如果比cand的最后一个数大，则递归DFS。比较简单的思路。 需要注意的点是，结果不能有重复数组，所以需要满足第19、6行的条件，并且用set去重。 第19行条件：比如样例[4,4,6,7,7,8,9,10]，第一个4为起点的DFS的结果已经包含第二个4为起点的DFS结果，所以需要第19行。 第6行条件：比如样例[4,4,6,7,7,8,9,10]，从6开始DFS时，遇到第一个7和遇到第二个7后续DFS的结果都是一样的，所以需要第6行。 set去重：还会遇到这样的样例比如样例[4,6,7,4,8,9,10]，第一个4DFS的结果包含了第二个4DFS的结果，但是这两个4不相邻，所以不能被第19行的条件防止重复，只能用set去重了。 代码如下： [cpp] class Solution { private: void dfs(set<vector<int>>& ans, vector<int>& nums, vector<int>& cand, int start){ if(cand.size() >= 2)ans.insert(cand); for(int i = start + 1; i < nums.size(); ++i){ if(i == start + 1 || nums[i] != nums[i – 1]){ if(nums[i] >= cand[cand.size() – 1]){ cand.push_back(nums[i]); dfs(ans, nums, cand, i); cand.pop_back(); } } } } public: vector<vector<int>> findSubsequences(vector<int>& nums) { set<vector<int>> ans; for(int i = 0; i < nums.size(); ++i){ if(i == 0 || nums[i] != nums[i-1]){ vector<int> cand = {nums[i]}; dfs(ans, nums, cand, i); } } return vector<vector<int>>(ans.begin(), ans.end()); } }; [/cpp] 本代码提交AC，用时269MS。]]>