Постановка задачи
Имея два целых числа n и k, вернуть все возможные комбинации k чисел из диапазона [1, n].
Вы можете вернуть ответ в любом порядке.
Постановка задачи взята с: https://leetcode.com/problems/combinations/.
Пример 1:
Input: n = 4, k = 2
Output:
[
[2, 4],
[3, 4],
[2, 3],
[1, 2],
[1, 3],
[1, 4],
]
Пример 2:
Input: n = 1, k = 1
Output: [[1]]
Ограничения:
- 1 <= n <= 20
- 1 <= k <= n
Объяснение
Решение грубой силы
Подход грубой силы состоит в том, чтобы сгенерировать все возможные комбинации размера k для n элементов. Этот подход займет много времени, когда мы увеличим n.
Возвращение
Оптимизированное решение — использовать подход с возвратом. Мы создаем временный массив с именем current и продолжаем добавлять элементы, пока размер массива current не станет равным k.
Как только мы достигаем предела k, мы извлекаем последний элемент и выталкиваем следующий элемент. Мы повторяем те же шаги, пока не достигнем n.
Давайте проверим алгоритм, чтобы увидеть, как мы можем использовать эту формулу.
// 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()
Давайте проверим наши решения на C++, Golang и Javascript.
С++ решение
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; } };
Голанг решение
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-решение
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; };
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
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]]
Первоначально опубликовано на https://alkeshghorpade.me.