leetcode

commit 7030976084918117607c80b39c542ff1c0f6a941
parent aab0ccefae5496d4cff8c99b0f9844bc6e1fb35a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 12 Feb 2023 14:06:17 +0100

Algorithm II: Day 10

Diffstat:
A
Problems/0039.cpp
 | 
23
+++++++++++++++++++++++
A
Problems/0040.cpp
 | 
24
++++++++++++++++++++++++
A
Problems/0047.cpp
 | 
11
+++++++++++
M
README.md
 | 
4
+++-

4 files changed, 61 insertions(+), 1 deletion(-)
diff --git a/Problems/0039.cpp b/Problems/0039.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  vector<vector<int>> res;
+  vector<int> crnt;
+
+  void rec(vector<int> &candidates, int target, int sum, int start = 0) {
+    if (sum == target)
+      res.push_back(crnt);
+    else if (sum < target) {
+      for (int i = start; i < candidates.size(); i++) {
+        crnt.push_back(candidates[i]);
+        rec(candidates, target, sum + candidates[i], i);
+        crnt.pop_back();
+      }
+    }
+  }
+
+public:
+  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
+    sort(candidates.begin(), candidates.end());
+    rec(candidates, target, 0);
+    return res;
+  }
+};
diff --git a/Problems/0040.cpp b/Problems/0040.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  vector<vector<int>> res;
+  vector<int> crnt;
+
+  void rec(vector<int> &candidates, int target, int sum, int start = 0) {
+    if (sum == target)
+      res.push_back(crnt);
+    else if (sum < target) {
+      for (int i = start; i < candidates.size(); i++) {
+        if (i != start && candidates[i] == candidates[i - 1]) continue;
+        crnt.push_back(candidates[i]);
+        rec(candidates, target, sum + candidates[i], i + 1);
+        crnt.pop_back();
+      }
+    }
+  }
+
+public:
+  vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
+    sort(candidates.begin(), candidates.end());
+    rec(candidates, target, 0);
+    return res;
+  }
+};
diff --git a/Problems/0047.cpp b/Problems/0047.cpp
@@ -0,0 +1,11 @@
+class Solution {
+public:
+  vector<vector<int>> permuteUnique(vector<int> &nums) {
+    vector<vector<int>> res;
+    sort(nums.begin(), nums.end());
+    do {
+      res.push_back(nums);
+    } while (next_permutation(nums.begin(), nums.end()));
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -48,10 +48,13 @@ for solving problems.
 |  0034  |   Medium   | [Find First and Last Position of Element in Sorted Array](Problems/0034.cpp)                     |
 |  0035  |    Easy    | [Search Insert Position](Problems/0035.cpp)                                                      |
 |  0036  |   Medium   | [Valid Sudoku](Problems/0036.cpp)                                                                |
+|  0039  |   Medium   | [Combination Sum](Problems/0039.cpp)                                                             |
+|  0040  |   Medium   | [Combination Sum II](Problems/0040.cpp)                                                          |
 |  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)                                                                |
+|  0047  |   Medium   | [Permutations II ](Problems/0047.cpp)                                                            |
 |  0048  |   Medium   | [Rotate Image](Problems/0048.cpp)                                                                |
 |  0049  |   Medium   | [Group Anagrams](Problems/0049.cpp)                                                              |
 |  0053  |   Medium   | [Maximum Subarray](Problems/0053.cpp)                                                            |
@@ -427,4 +430,3 @@ for solving problems.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 |  2497  |   Medium   | [Maximum Star Sum of a Graph](Problems/2497.cpp)                                                 |
-