力扣算法题—077组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

  1 #include "_000库函数.h"
  2 
  3 
  4 //就是排列组合问题
  5 //但是是按顺序选，感觉很简单
  6 class Solution {
  7 public:
  8     vector<vector<int>> combine(int n, int k) {
  9         if (k > n || n < 1 || k < 1)return{};
 10         vector<vector<int>>res;
 11         vector<int>Num;
 12         for (int i = 0; i < n; ++i)Num.push_back(i + 1);
 13         vector<bool>Index(k, 1);//令标记位前三个为选中状态
 14         Index.insert(Index.end(), n - k, 0);//后面的 数字未被选中
 15         res.push_back(Print(Index, Num));//保存数据
 16 
 17         while (!hasDone(Index, n, k))
 18         {
 19             //从左到右扫描数组
 20             for (int i = 0; i < n - 1; i++)
 21             {
 22                 //找到第一个“10”组合将其变成"01"组合
 23                 if (Index[i] && !Index[i + 1])
 24                 {
 25                     Index[i] = false;
 26                     Index[i + 1] = true;
 27 
 28                     //将"01"组合左边的1移到最左边
 29                     int count = 0;
 30                     for (int j = 0; j < i; j++)
 31                     {
 32                         if (Index[j])
 33                         {
 34                             Index[j] = false;
 35                             Index[count++] = true;
 36                         }
 37                     }
 38                     res.push_back(Print(Index, Num));//保存数据
 39                     break;
 40                 }
 41             }
 42         }
 43         return res;
 44     }
 45     vector<int> Print(vector<bool>Index, vector<int>Num) {
 46         vector<int>v;
 47         for (int i = 0; i < Index.size(); ++i)
 48             if (Index[i])v.push_back(Num[i]);
 49         return v;
 50     }
 51 
 52     //检查最后k个位置是否已全变成0
 53     bool hasDone(vector<bool>index, int n, int k)
 54     {
 55         for (int i = n - 1; i >= n - k; i--)
 56             if (!index[i]) return false;
 57         return true;
 58     }
 59 };
 60 
 61 
 62 //使用深度搜索策略
 63 class Solution {
 64 public:
 65     vector<vector<int>> combine(int n, int k) {
 66         if (k > n || n < 1 || k < 1)return{};
 67         vector<vector<int>>res;
 68         vector<int>v;
 69         helper(n, k, 1, v, res);
 70         return res;
 71     }
 72 
 73     void helper(int n, int k, int level, vector<int>&v, vector<vector<int>>&res) {
 74         if (v.size() == k) {
 75             res.push_back(v);
 76             return;
 77         }
 78         for (int i = level; i <= n; ++i) {
 79             v.push_back(i);
 80             helper(n, k, i + 1, v, res);
 81             v.pop_back();
 82         }
 83     }
 84 };
 85 
 86 //我们再来看一种递归的写法，此解法没用helper当递归函数，
 87 //而是把本身就当作了递归函数，写起来十分的简洁，也是非常有趣的一种解法。
 88 //这个解法用到了一个重要的性质 C(n, k) = C(n - 1, k - 1) + C(n - 1, k)，
 89 //这应该在我们高中时候学排列组合的时候学过吧，博主也记不清了。
 90 //总之，翻译一下就是，在n个数中取k个数的组合项个数，
 91 //等于在n - 1个数中取k - 1个数的组合项个数再加上在n - 1个数中取k个数的组合项个数之和。
 92 //这里博主就不证明了，因为我也不会，就直接举题目中的例子来说明吧：
 93 //C(4, 2) = C(3, 1) + C(3, 2)
 94 //我们不难写出 C(3, 1) 的所有情况：[1], [2], [3]，
 95 //还有 C(3, 2) 的所有情况：[1, 2], [1, 3], [2, 3]。
 96 //我们发现二者加起来为6，正好是 C(4, 2) 的个数之和。
 97 //但是我们仔细看会发现，C(3, 2)的所有情况包含在 C(4, 2) 之中，
 98 //但是 C(3, 1) 的每种情况只有一个数字，而我们需要的结果k = 2，
 99 //其实很好办，每种情况后面都加上4，于是变成了：[1, 4], [2, 4], [3, 4]，
100 //加上C(3, 2) 的所有情况：[1, 2], [1, 3], [2, 3]，正好就得到了 n = 4, k = 2 的所有情况了。
101 //参见代码如下：
102 
103 class Solution {
104 public:
105     vector<vector<int>> combine(int n, int k) {
106         if (k > n || k < 0)return{};
107         if (k == 0)return { {} };
108         vector<vector<int>>res = combine(n - 1, k - 1);
109         for (auto &a : res)a.push_back(n);
110         for (auto &a : combine(n - 1, k))res.push_back(a);
111         return res;
112     }
113 };
114 
115 
116 
117 void T077() {
118     Solution s;
119     vector<vector<int>>v;
120     v = s.combine(4, 2);
121     for (auto a : v) {
122         for (auto b : a)
123             cout << b << "  ";
124         cout << endl;
125     }
126 }