leetcode

commit d0f6ac3a11d8c8822d731f9e0fc35e4b0e1e68cf
parent fc4d87afe2816ede73fa6d7daeb3dc887c7ac0e3
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 20 Jan 2023 20:42:54 +0100

Daily Problem

Diffstat:
A
Problems/0491.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/0491.cpp b/Problems/0491.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  vector<vector<int>> res;
+  vector<int> seq;
+
+public:
+  vector<vector<int>> findSubsequences(vector<int> &nums) {
+    dfs(nums, 0);
+    return res;
+  }
+
+  void dfs(vector<int> &nums, int pos) {
+    if (seq.size() > 1) res.push_back(seq);
+    unordered_set<int> hash;
+    for (int i = pos; i < nums.size(); i++) {
+      if ((seq.empty() || nums[i] >= seq.back()) && !hash.count(nums[i])) {
+        seq.push_back(nums[i]);
+        dfs(nums, i + 1);
+        seq.pop_back();
+        hash.insert(nums[i]);
+      }
+    }
+  }
+};
diff --git a/README.md b/README.md
@@ -152,6 +152,7 @@ for solving problems.
 |  0450  |   Medium   | [Delete Node in a BST](Problems/0450.cpp)                                                        |
 |  0452  |   Medium   | [Minimum Number of Arrows to Burst Balloons](Problems/0452.cpp)                                  |
 |  0485  |    Easy    | [Max Consecutive Ones](Problems/0485.cpp)                                                        |
+|  0491  |   Medium   | [Non-decreasing Subsequences](Problems/0491.cpp)                                                 |
 |  0494  |   Medium   | [Target Sum](Problems/0494.cpp)                                                                  |
 |  0496  |   Medium   | [Next Greater Element I](Problems/0496.cpp)                                                      |
 |  0498  |   Medium   | [Diagonal Traverse](Problems/0498.cpp)                                                           |