给定两个整数 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 > combine(int n, int k) { 9 if (k > n || n < 1 || k < 1)return{}; 10 vector >res; 11 vector Num; 12 for (int i = 0; i < n; ++i)Num.push_back(i + 1); 13 vector 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 Print(vector Index, vector Num) { 46 vector 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 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 > combine(int n, int k) { 66 if (k > n || n < 1 || k < 1)return{}; 67 vector >res; 68 vector v; 69 helper(n, k, 1, v, res); 70 return res; 71 } 72 73 void helper(int n, int k, int level, vector &v, vector >&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 > combine(int n, int k) {106 if (k > n || k < 0)return{};107 if (k == 0)return { {} };108 vector >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 >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 }