leetcode

commit 080fd5e402784bf5a9671c93e60439957a2b6d6c
parent 30cb3fa1b382e513024b3f6c934a0f7d9fbbddd2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 11 Feb 2023 12:20:27 +0100

Algorithm II: Day 9

Diffstat:
A
Problems/0078.cpp
 | 
15
+++++++++++++++
A
Problems/0090.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/0078.cpp b/Problems/0078.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  vector<vector<int>> subsets(vector<int> &nums) {
+    vector<vector<int>> res;
+
+    res.push_back({});
+    for (int num : nums) {
+      for (int i = res.size() - 1; i >= 0; i--) {
+        res.push_back(res[i]);
+        res.back().push_back(num);
+      }
+    }
+    return res;
+  }
+};
diff --git a/Problems/0090.cpp b/Problems/0090.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+  vector<vector<int>> subsetsWithDup(vector<int> &nums) {
+    sort(nums.begin(), nums.end());
+    vector<vector<int>> res = {{}, {nums[0]}};
+
+    int prev = 1;
+    for (int i = 1; i < nums.size(); i++) {
+      int end = nums[i] == nums[i - 1] ? prev : 0;
+      prev = res.size();
+      for (int j = res.size() - 1; j >= end; j--) {
+        res.push_back(res[j]);
+        res.back().push_back(nums[i]);
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -71,10 +71,12 @@ for solving problems.
 |  0074  |   Medium   | [Search a 2D Matrix](Problems/0074.cpp)                                                          |
 |  0075  |   Medium   | [Sort Colors](Problems/0075.cpp)                                                                 |
 |  0077  |   Medium   | [Combinations](Problems/0077.cpp)                                                                |
+|  0078  |   Medium   | [Subsets](Problems/0078.cpp)                                                                     |
 |  0082  |   Medium   | [Remove Duplicates from Sorted List II](Problems/0082.cpp)                                       |
 |  0083  |    Easy    | [Remove Duplicates from Sorted List](Problems/0083.cpp)                                          |
 |  0084  |    Hard    | [Largest Rectangle in Histogram](Problems/0084.cpp)                                              |
 |  0088  |    Easy    | [Merge Sorted Array](Problems/0088.cpp)                                                          |
+|  0090  |   Medium   | [Subsets II](Problems/0090.cpp)                                                                  |
 |  0091  |   Medium   | [Decode Ways](Problems/0091.cpp)                                                                 |
 |  0093  |   Medium   | [Restore IP Addresses](Problems/0093.cpp)                                                        |
 |  0094  |    Easy    | [Binary Tree Inorder Traversal](Problems/0094.cpp)                                               |