# Combinations Problem

## Description

LeetCode Problem 77.

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

You may return the answer in any order.

Example 1:

``````1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
``````

Example 2:

``````1
2
Input: n = 1, k = 1
Output: [[1]]
``````

Constraints:

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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int>> ans;

void dfs(vector<int>& candidates, vector<int>& comb, int target, int idx) {
if (target == 0)
ans.push_back(comb);
if (target <= 0)
return;

for (int i = idx; i < candidates.size(); i ++) {
comb.push_back(candidates[i]);
dfs(candidates, comb, target-1, i+1);
comb.pop_back();
}
}

vector<vector<int>> combine(int n, int k) {
vector<int> candidates;
for (int i = 1; i <= n; i ++) candidates.push_back(i);
vector<int> comb;

dfs(candidates, comb, k, 0);

return ans;
}
};
``````