# 77. Combinations

Given two integers `n` and `k`, return all possible combinations of `k` numbers chosen from the range `[1, n]`.

You may return the answer in any order.

Example 1:

``````Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
``````

Example 2:

``````Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
``````

Constraints:

• `1 <= n <= 20`
• `1 <= k <= n`

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
dfs(n, k, 1, cur, res);
return res;
}
void dfs(int n, int k, int level, vector<int>& cur, vector<vector<int>>& res) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = level; i <= n; ++i) {
cur.push_back(i);
dfs(n, k, i + 1, cur, res);
cur.pop_back();
}
}
};
``````

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

C(4, 2) = C(3, 1) + C(3, 2)

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k > n || k < 0) return {};
if (k == 0) return {{}};
vector<vector<int>> res = combine(n - 1, k - 1);
for (auto &a : res) a.push_back(n);
for (auto &a : combine(n - 1, k)) res.push_back(a);
return res;
}
};
``````

``````0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop
``````

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur(k);
int i = 0;
while (i >= 0) {
++cur[i];
if (cur[i] > n) {
--i;
} else if (i == k - 1) {
res.push_back(cur);
} else {
++i;
cur[i] = cur[i - 1];
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/77

Combination Sum

Permutations

https://leetcode.com/problems/combinations

https://leetcode.com/problems/combinations/discuss/27015/3-ms-Java-Solution

https://leetcode.com/problems/combinations/discuss/27002/Backtracking-Solution-Java

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation