491.递增子序列

原题链接：491.递增子序列

思路：
遍历所有结点，并且遍历一个就将path给push进result中，因为每增加一个结点就代表有一个新的子序列。
要考虑去重 所以使用unorderedset uset。
将每层使用过的元素添加进uset中，代表本层后面不能再使用相同元素。
如果子序列为空且nums[i]的值小于序列的最后一个值(不满足要求)，或者nums[i]在uset中出现过，那么就跳过本层的该元素，因为该元素在之前使用过。

全代码：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex)
    {
        if(path.size() > 1){//将所有子序列添加进去
            result.push_back(path);
        }
        unordered_set<int> uset; //使用set进行排序
        for(int i =  startIndex; i <nums.size(); i++)
        {
            if(!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end())
            {
                continue;
            }
            uset.insert(nums[i]); //记录该元素在本层使用过
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28