LC77.组合

原题链接
原题链接

思路1：回溯

  • “叶子节点是数组的最后一个元素”类型的回溯模板题

  • 两种回溯办法：第一种，选择当前位置或者不不选择当前位置；第二种，遍历数组进行回溯

    代码1：

  • 数组的最后一个元素当作叶子节点

    1. class Solution {
    2. public:
    3.  void backTrace(vector<vector<int>>& all_comb, vector<int>& cur_comb, int cur_sub, int n, int k) {
    4.      if (cur_comb.size() == k) {
    5.          all_comb.push_back(cur_comb);
    6.          return;
    7.      }
    9.      if (cur_sub == n + 1) {
    10.          return;
    11.      }
    13.      for (int i = cur_sub; i <= n; i++) {
    14.          cur_comb.push_back(i);
    15.          backTrace(all_comb, cur_comb, i + 1, n, k);
    16.          cur_comb.pop_back();
    17.      }
    18.  }
    20.  vector<vector<int>> combine(int n, int k) {
    21.      vector<vector<int>> all_comb;
    22.      vector<int> cur_comb;
    23.      backTrace(all_comb, cur_comb, 1, n, k);
    24.      return all_comb;
    25.  }
    26. };

  • 选择当前位置或者不选

  1. class Solution {
  2. public:
  3.     void dfs(int index, int k, int n, vector<vector<int>>& res, vector<int>& nums) {
  4.         if (nums.size() == k) {
  5.             res.push_back(nums);
  6.             return ;
  7.         }
  9.         if (nums.size() + (n - index) < k) {
  10.             return;
  11.         }
  13.     // 选择当前位置
  14.         nums.push_back(index + 1);
  15.         dfs(index + 1, k, n, res, nums);
  16.         nums.pop_back();
  18.                 // 不选当前位置
  19.         dfs(index + 1, k ,n, res, nums);
  20.     }
  22.     vector<vector<int>> combine(int n, int k) {
  23.         vector<vector<int>> res;
  24.         vector<int> nums;
  26.         dfs(0, k, n, res, nums);
  27.         return res;
  28.     }
  29. };

思路2：二进制暴力枚举

  • 对situation进行枚举
  1. // n == 2
  2. // S 最大取到 (2 ^ n) - 1
  3. // 00 01 10 11   （100取不到）
  4. for (int S = 0; S < (1 << n); S++)
  • 从右往左读取位置（低位为1）
  1. // 如果第i低位是1，表示选取这个位置
  2. if (S & (1 << i))

代码2：

  1. class Solution {
  2. public:
  3.     int getBinNum(int num) {
  4.         int cnt = 0;
  5.         for (int i = 0; i < 20; i++) {
  6.             if (num & 1) {
  7.                 cnt += 1;
  8.             }
  9.             num >>= 1;
  10.         }
  12.         return cnt;
  13.     }
  15.     vector<vector<int>> combine(int n, int k) {
  16.         // n == 2
  17.         // S 最大取到 (2 ^ n) - 1
  18.         // 00 01 10 11   （100取不到）
  20.         vector<vector<int>> ans;
  21.         for (int S = 0; S < (1 << n); S++) {
  22.             if (getBinNum(S) == k) {
  23.                 vector<int> cur_s;
  24.                 for (int i = 0; i < n; i++) {
  25.                     if (S & (1 << i)) {
  26.                         cur_s.push_back(i + 1);
  27.                     }
  28.                 }
  30.                 ans.push_back(cur_s);
  31.             }
  32.         }
  33.         return ans;
  34.     }
  35. };