LeetCode — Combinations
Published in
4 min readMay 1, 2022
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 <= nExplanation
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> currentStep 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 9Step 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 resultSo we return the result as [[1, 2], [1, 3], [2, 3]]
Originally published at https://alkeshghorpade.me.
