本文主要是介绍77. Combinations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
77. 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ]
解法一：
//时间复杂度O(n^k), 空间复杂度O(k*C(n,k))
class Solution {
public:void combine(vector<vector<int>>& res, vector<int>& cur, unordered_set<int>& us, int n, int k) {if(cur.size() == k) {res.push_back(cur);return;}for(int i = 1; i <= n; i++) {if(us.count(i) || !cur.empty() && i < cur[cur.size() - 1]) continue;cur.push_back(i);us.insert(i);combine(res, cur, us, n, k);cur.pop_back();us.erase(i);}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> cur;unordered_set<int> us;combine(res, cur, us, n, k);return res;}
};解法二：
//时间复杂度O(n!*n), 空间复杂度O(k*C(n,k))
class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<int> nums(n);vector<int> selector(n);for(int i = 0; i < n; i++) {nums[i] = i + 1;if(i < k) selector[i] = 1;else selector[i] = 0;}vector<vector<int>> res;do {vector<int> temp;for(int i = 0; i < n; i++) {if(selector[i] == 1) {temp.push_back(nums[i]);}}res.push_back(temp);} while(prev_permutation(selector.begin(), selector.end()));return res;}
};解法一与第31、39、40题的思路一样，递归地遍历每一种情况，只取数组元素递增的作为解。每一层有n种情况要遍历，一共有k层，时间复杂度O(n^k)。
解法二是看陈硕的书上给出的解法，先设置一个列表nums = [1,2,3,...,n]，再给一个列表selector = [1,1,1,...,0,0,0]（有k个1），对selector作全排列，然后以它为蒙板对nums进行过滤（具体说就是当selector[i]==1时，取nums[i]），得到一个子序列，就是组合中一种的情况。这种要对n长的数组作全排列，时间复杂度O(n!*n)
2019/10/23 10:53
这篇关于77. Combinations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
