Сложность: medium
Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].
Ответ можно вернуть в любом порядке.
Пример:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
👨💻 Алгоритм:
1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.
2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.
3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.
😎 Решение:
func combine(_ n: Int, _ k: Int) -> [[Int]] {
var ans = [[Int]]()
func backtrack(_ curr: inout [Int], _ firstNum: Int) {
if curr.count == k {
ans.append(curr)
return
}
let need = k - curr.count
let remain = n - firstNum + 1
let available = remain - need
for num in firstNum...(firstNum + available) {
curr.append(num)
backtrack(&curr, num + 1)
curr.removeLast()
}
}
var initial = [Int]()
backtrack(&initial, 1)
return ans
}Ставь 👍 и забирай 📚 Базу знаний