leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0077.cpp (1730B)

0 // Recursive solution 1 class Solution { 2 vector<int> crnt; 3 vector<vector<int>> res; 4 void rec(int s, int n, int k) { 5 if (s > n + 1) return; 6 if (!k) { 7 res.push_back(crnt); 8 return; 9 } 10 11 crnt.push_back(s); 12 rec(s + 1, n, k - 1); 13 crnt.pop_back(); 14 rec(s + 1, n, k); 15 } 16 17 public: 18 vector<vector<int>> combine(int n, int k) { 19 rec(1, n, k); 20 return res; 21 } 22 }; 23 24 // Iterative solution 25 class Solution { 26 public: 27 vector<vector<int>> combine(int n, int k) { 28 vector<vector<int>> res; 29 vector<int> iter; 30 iter.reserve(k); 31 for (int mask = (1 << k) - 1; mask < 1 << n; mask++) { 32 if (__builtin_popcount(mask) != k) continue; 33 34 for (int crnt = mask, idx; crnt; crnt ^= 1 << (idx - 1)) { 35 idx = __builtin_ffs(crnt); 36 iter.push_back(idx); 37 } 38 res.push_back(iter); 39 iter.clear(); 40 } 41 return res; 42 } 43 }; 44 45 // Improved iterative solution with bit twiddling 46 class Solution { 47 int twiddle(int v) { 48 int t = v | (v - 1); 49 int w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 50 return w; 51 } 52 53 public: 54 vector<vector<int>> combine(int n, int k) { 55 vector<vector<int>> res; 56 vector<int> iter; 57 iter.reserve(k); 58 for (int mask = (1 << k) - 1; mask < 1 << n; mask = twiddle(mask)) { 59 for (int crnt = mask, idx; crnt; crnt ^= 1 << (idx - 1)) { 60 idx = __builtin_ffs(crnt); 61 iter.push_back(idx); 62 } 63 res.push_back(iter); 64 iter.clear(); 65 } 66 return res; 67 } 68 };