## DEV Community is a community of 872,863 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Combinations

### 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: []
``````

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 = 

backtrack(result, current, n, k, i + 1)
backtrack([[]], , 3, 2, 0 + 1)
backtrack([[]], , 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 = 

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 = 

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 = 

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 = 

backtrack(result, current, n, k, i + 1)
backtrack([[1, 2], [1, 3]], , 3, 2, 1 + 1)
backtrack([[1, 2], [1, 3]], , 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 = 

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 = 

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]]
``````