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