### Problem statement

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**.

Problem statement taken from: https://leetcode.com/problems/combinations/.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

```
- 1 <= n <= 20
- 1 <= k <= n
```

### Explanation

#### Brute force solution

The brute force approach is to generate all possible combinations of size

k for the n elements.

This approach will consume a lot of time when we increase **n**.

#### Backtracking

An optimized solution is to use a backtracking approach.

We create a temporary array called **current**

and

keep adding the elements till the size of the **current** array is equal to

**k**.

Once we reach the limit **k**, we pop the last element

and

push the next element. We repeat the same steps till we reach **n**.

Let's check the algorithm to see how we can use this formula.

```
// combine(n, k)
- initialize result, current
- backtrack(result, current, n, k, 0)
- return result
// backtrack(result, current, n, k, pos)
- if current.size() == k
- result.push_back(current)
- return
- loop for i = pos; i < n; i++
- current.push_back(i + 1)
- backtrack(result, current, n, k, i + 1)
- current.pop_back()
```

Let's check out our solutions in **C++**, **Golang**, and **Javascript**.

#### C++ solution

```
class Solution {
public:
void backtrack(vector<vector<int>> &result, vector<int> current, int n, int k, int pos) {
if(current.size() == k) {
result.push_back(current);
return;
}
for(int i = pos; i < n; i++) {
current.push_back(i + 1);
backtrack(result, current, n, k, i + 1);
current.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> current;
backtrack(result, current, n, k, 0);
return result;
}
};
```

#### Golang solution

```
func backtrack(result *[][]int, current []int, n, k, pos int) {
if len(current) == k {
*result = append(*result, append([]int{}, current...))
return
}
for i := pos; i < n; i++ {
current = append(current, i + 1)
backtrack(result, current, n, k, i + 1)
current = current[:len(current) - 1]
}
}
func combine(n int, k int) [][]int {
result := make([][]int, 0)
backtrack(&result, []int{}, n, k, 0)
return result
}
```

#### Javascript solution

```
var combine = function(n, k) {
let result = [];
const backtrack = (pos, n, k, current) => {
if(current.length === k){
result.push([...current]);
}
if(pos > n){
return;
}
for(let i = pos; i <= n; i++){
current.push(i);
backtrack(i + 1, n, k, current);
current.pop();
}
}
backtrack(1, n, k, []);
return result;
};
```

Let's dry-run our algorithm to see how the solution works.

```
Input: n = 3, k = 2
// combine function
Step 1: vector<vector<int>> result
vector<int> current
Step 2: backtrack(result, current, n, k, 0)
backtrack([[]], [], 3, 2, 0)
// backtrack function
Step 3: current.size() == k
0 == 2
false
loop for i = pos; i < n;
i = 0
0 < 3
true
current.push_back(i + 1)
current.push_back(0 + 1)
current.push_back(1)
current = [1]
backtrack(result, current, n, k, i + 1)
backtrack([[]], [1], 3, 2, 0 + 1)
backtrack([[]], [1], 3, 2, 1)
Step 4: current.size() == k
1 == 2
false
loop for i = pos; i < n;
i = 1
1 < 3
true
current.push_back(i + 1)
current.push_back(1 + 1)
current.push_back(2)
current = [1, 2]
backtrack(result, current, n, k, i + 1)
backtrack([[]], [1, 2], 3, 2, 1 + 1)
backtrack([[]], [1, 2], 3, 2, 2)
Step 5: current.size() == k
2 == 2
true
result.push_back(current)
result.push_back([1, 2])
result = [[1, 2]]
return
We backtrack to step 4 and move to the next step.
Step 6: current.pop_back()
current = [1, 2]
current = [1]
i++
i = 2
loop for i = pos; i < n;
i = 2
2 < 3
true
current.push_back(i + 1)
current.push_back(2 + 1)
current.push_back(3)
current = [1, 3]
backtrack(result, current, n, k, i + 1)
backtrack([[1, 2]], [1, 3], 3, 2, 2 + 1)
backtrack([[1, 2]], [1, 3], 3, 2, 3)
Step 7: current.size() == k
2 == 2
true
result.push_back(current)
result.push_back([1, 3])
result = [[1, 2], [1, 3]]
return
We backtrack to step 6 and move to the next step.
Step 8: current.pop_back()
current = [1, 3]
current = [1]
i++
i = 3
loop for i = pos; i < n;
i = 3
3 < 3
false
We backtrack to step 3 and move to the next step.
Step 9: current.pop_back()
current = [1]
current = []
i++
i = 1
loop for i = pos; i < n;
i = 1
1 < 3
true
current.push_back(i + 1)
current.push_back(1 + 1)
current.push_back(2)
current = [2]
backtrack(result, current, n, k, i + 1)
backtrack([[1, 2], [1, 3]], [2], 3, 2, 1 + 1)
backtrack([[1, 2], [1, 3]], [2], 3, 2, 2)
Step 10: current.size() == k
1 == 2
false
loop for i = pos; i < n;
i = 2
2 < 3
true
current.push_back(i + 1)
current.push_back(2 + 1)
current.push_back(3)
current = [2, 3]
backtrack(result, current, n, k, i + 1)
backtrack([[1, 2], [1, 3]], [2, 3], 3, 2, 2 + 1)
backtrack([[1, 2], [1, 3]], [2, 3], 3, 2, 3)
Step 11: current.size() == k
2 == 2
true
result.push_back(current)
result.push_back([2, 3])
result = [[1, 2], [1, 3], [2, 3]]
return
We backtrack to step 10 and move to the next step.
Step 12: current.pop_back()
current = [2, 3]
current = [2]
i++
i = 3
loop for i = pos; i < n;
i = 3
3 < 3
false
We backtrack to step 9
Step 13: current.pop_back()
current = [2]
current = []
i++
i = 3
loop for i = pos; i < n;
i = 3
3 < 3
false
We backtrack to combine function and return result
// combine function
Step 14: return result
So we return the result as [[1, 2], [1, 3], [2, 3]]
```

## Top comments (0)