leetcode

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 };