leetcode

commit dd63796ba7593aa00c2713806779db89a2da630b
parent ed4d5136e5d7161ea0da3b487d41bf822855c3a4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  1 Aug 2023 20:50:46 +0200

Improved Daily Problem

Diffstat:
M
Problems/0077.cpp
 | 
58
+++++++++++++++++++++++++++++++++++++++++++++++++++++-----

1 file changed, 53 insertions(+), 5 deletions(-)
diff --git a/Problems/0077.cpp b/Problems/0077.cpp
@@ -1,16 +1,18 @@
+// Recursive solution
 class Solution {
   vector<int> crnt;
   vector<vector<int>> res;
   void rec(int s, int n, int k) {
+    if (s > n + 1) return;
     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();
-    }
+
+    crnt.push_back(s);
+    rec(s + 1, n, k - 1);
+    crnt.pop_back();
+    rec(s + 1, n, k);
   }
 
 public:
@@ -19,3 +21,49 @@ public:
     return res;
   }
 };
+
+// Iterative solution
+class Solution {
+public:
+  vector<vector<int>> combine(int n, int k) {
+    vector<vector<int>> res;
+    vector<int> iter;
+    iter.reserve(k);
+    for (int mask = (1 << k) - 1; mask < 1 << n; mask++) {
+      if (__builtin_popcount(mask) != k) continue;
+
+      for (int crnt = mask, idx; crnt; crnt ^= 1 << (idx - 1)) {
+        idx = __builtin_ffs(crnt);
+        iter.push_back(idx);
+      }
+      res.push_back(iter);
+      iter.clear();
+    }
+    return res;
+  }
+};
+
+// Improved iterative solution with bit twiddling
+class Solution {
+  int twiddle(int v) {
+    int t = v | (v - 1);
+    int w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
+    return w;
+  }
+
+public:
+  vector<vector<int>> combine(int n, int k) {
+    vector<vector<int>> res;
+    vector<int> iter;
+    iter.reserve(k);
+    for (int mask = (1 << k) - 1; mask < 1 << n; mask = twiddle(mask)) {
+      for (int crnt = mask, idx; crnt; crnt ^= 1 << (idx - 1)) {
+        idx = __builtin_ffs(crnt);
+        iter.push_back(idx);
+      }
+      res.push_back(iter);
+      iter.clear();
+    }
+    return res;
+  }
+};