leetcode

commit 8a1900f1c2c4c261b35096e570a6035dcd966a49
parent d992e1282953f53018a0cd3f4305a3e2c078b2fd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 31 Jan 2023 16:31:52 +0100

Algorithm I: Day 11

Diffstat:
A
Problems/0046.cpp
 | 
25
+++++++++++++++++++++++++
A
Problems/0077.cpp
 | 
21
+++++++++++++++++++++
A
Problems/0784.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
3
+++

4 files changed, 70 insertions(+), 0 deletions(-)
diff --git a/Problems/0046.cpp b/Problems/0046.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  vector<vector<int>> res;
+  vector<int> crnt;
+  vector<bool> seen;
+
+  void rec(vector<int> &nums, int n) {
+    if (n == nums.size()) {
+      res.push_back(crnt);
+      return;
+    }
+    for (int i = 0; i < nums.size(); i++) {
+      if (seen[i]) continue;
+      seen[i] = true, crnt.push_back(nums[i]);
+      rec(nums, n + 1);
+      seen[i] = false, crnt.pop_back();
+    }
+  }
+
+public:
+  vector<vector<int>> permute(vector<int> &nums) {
+    seen.resize(nums.size());
+    rec(nums, 0);
+    return res;
+  }
+};
diff --git a/Problems/0077.cpp b/Problems/0077.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  vector<int> crnt;
+  vector<vector<int>> res;
+  void rec(int s, int n, int k) {
+    if (!k) {
+      res.push_back(crnt);
+      return;
+    }
+    for (int i = s; i <= n; i++) {
+      crnt.push_back(i);
+      rec(i + 1, n, k - 1);
+      crnt.pop_back();
+    }
+  }
+
+public:
+  vector<vector<int>> combine(int n, int k) {
+    rec(1, n, k);
+    return res;
+  }
+};
diff --git a/Problems/0784.cpp b/Problems/0784.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  vector<string> res;
+
+  void rec(string &s, int st, string crnt) {
+    while (st < s.size() && !isalpha(s[st])) crnt += s[st++];
+    if (st == s.size()) {
+      res.push_back(crnt);
+      return;
+    }
+
+    char c = tolower(s[st]);
+    rec(s, st + 1, crnt + c);
+    rec(s, st + 1, crnt + (char)toupper(c));
+  }
+
+public:
+  vector<string> letterCasePermutation(string s) {
+    rec(s, 0, "");
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -46,6 +46,7 @@ for solving problems.
 |  0042  |   Medium   | [Trapping Rain Water](Problems/0011.cpp)                                                         |
 |  0043  |   Medium   | [Multiply Strings](Problems/0043.cpp)                                                            |
 |  0045  |   Medium   | [Jump Game II](Problems/0045.cpp)                                                                |
+|  0046  |   Medium   | [Permutations](Problems/0046.cpp)                                                                |
 |  0049  |   Medium   | [Group Anagrams](Problems/0049.cpp)                                                              |
 |  0053  |   Medium   | [Maximum Subarray](Problems/0053.cpp)                                                            |
 |  0054  |   Medium   | [Spiral Matrix](Problems/0054.cpp)                                                               |
@@ -59,6 +60,7 @@ for solving problems.
 |  0067  |    Easy    | [Add Binary](Problems/0067.cpp)                                                                  |
 |  0070  |    Easy    | [Climbing Stairs](Problems/0070.cpp)                                                             |
 |  0074  |   Medium   | [Search a 2D Matrix](Problems/0074.cpp)                                                          |
+|  0077  |   Medium   | [Combinations](Problems/0077.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)                                                          |
@@ -228,6 +230,7 @@ for solving problems.
 |  0747  |    Easy    | [Largest Number At Least Twice of Others](Problems/0747.cpp)                                     |
 |  0752  |   Medium   | [Open the Lock](Problems/0752.cpp)                                                               |
 |  0783  |    Easy    | [Minimum Distance Between BST Nodes](Problems/0783.cpp)                                          |
+|  0784  |   Medium   | [Letter Case Permutation](Problems/0784.cpp)                                                     |
 |  0785  |   Medium   | [Is Graph Bipartite?](Problems/0785.cpp)                                                         |
 |  0787  |   Medium   | [Cheapest Flights Within K Stops](Problems/0787.cpp)                                             |
 |  0797  |   Medium   | [All Paths From Source to Target](Problems/0797.cpp)                                             |