-
Notifications
You must be signed in to change notification settings - Fork 0
/
491. Increasing Subsequences 2.cpp
39 lines (31 loc) · 1 KB
/
491. Increasing Subsequences 2.cpp
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
29
30
31
32
33
34
35
36
37
38
39
// https://leetcode.com/problems/increasing-uniqueSubsequences/
class Solution
{
vector<vector<int>> result;
set<vector<int>> uniqueSubsequences;
public:
vector<vector<int>> findSubsequences(vector<int> &nums)
{
vector<int> current;
dfs(nums, current, 0);
for (const vector<int> &uniqueSubsequence : uniqueSubsequences)
result.push_back(uniqueSubsequence);
return result;
}
void dfs(vector<int> &nums, vector<int> ¤t, int start)
{
if (current.size() >= 2 && uniqueSubsequences.find(current) == uniqueSubsequences.end())
uniqueSubsequences.insert(current);
if (start >= nums.size())
return;
for (int i = start; i < nums.size(); ++i)
{
if (current.empty() || (!current.empty() && nums[i] >= current.back()))
{
current.push_back(nums[i]);
dfs(nums, current, i + 1);
current.pop_back();
}
}
}
};