# LeetCode77. Combinations（递归 / 回溯）

## LeetCode77. Combinations（递归 / 回溯）

• Medium
• Accepted：193,768
• Submissions：413,947

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

### 链接

https://leetcode.com/problems/combinations

### 代码

• Runtime: 88 ms, faster than 62.27% of C++ online submissions for Combinations.
• Memory Usage: 12.8 MB, less than 39.01% of C++ online submissions for Combinations.
class Solution {
private:
vector <vector<int>> ans;
void solve(int n, int k, int start, vector <int> & comb)
{
if (comb.size() == k)
{
ans.push_back(comb);
return ;
}
for (int i = start; i <= n; ++i)
{
comb.push_back(i);
solve(n, k, i + 1, comb);
comb.pop_back(); // 回溯
}
}

public:
vector<vector<int>> combine(int n, int k) {
ans.clear();
if (n == 0 || k == 0)
return ans;
vector <int> comb;
solve(n, k, 1, comb);
return ans;
}
};
• Runtime: 64 ms, faster than 92.56% of C++ online submissions for Combinations.
• Memory Usage: 12.8 MB, less than 38.63% of C++ online submissions for Combinations.
class Solution {
private:
vector <vector<int>> ans;
void solve(int n, int k, int start, vector <int> & comb)
{
if (comb.size() == k)
{
ans.push_back(comb);
return ;
}
for (int i = start; i <= n - (k - comb.size()) + 1; ++i) // 剪枝
{
comb.push_back(i);
solve(n, k, i + 1, comb);
comb.pop_back(); // 回溯
}
}

public:
vector<vector<int>> combine(int n, int k) {
ans.clear();
if (n == 0 || k == 0)
return ans;
vector <int> comb;
solve(n, k, 1, comb);
return ans;
}
};
• Runtime: 55 ms, faster than 33.22% of C++ online submissions for Combinations.
• Memory Usage: 18 MB, less than 32.92% of C++ online submissions for Combinations.
class Solution
{
public:
vector<vector<int>> combine(int n, int k)
{
vector<vector<int>> result;
if (n == 0 || k == 0)
return result;
vector<int> subset;
getSubsets(n, k, 1, subset, result);
return result;
}
void getSubsets(int &n, int &k, int index, vector<int> &subset, vector<vector<int>> &result)
{
if (subset.size() == k)
{
result.push_back(subset);
return ;
}
else if (index <= n)
{
// 不选
getSubsets(n, k, index + 1, subset, result);
// 选
subset.push_back(index);
getSubsets(n, k, index + 1, subset, result);
subset.pop_back();
}
}
};