Сложность: medium
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
👨💻 Алгоритм:
1⃣Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.
2⃣Рекурсивная обработка:
В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов.
Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки.
Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата.
3⃣Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.
😎 Решение:
class Solution {
func backtrack(_ remain: Int, _ k: Int, _ comb: inout [Int], _ nextStart: Int, _ results: inout [[Int]]) {
if remain == 0 && comb.count == k {
results.append(comb)
return
} else if remain < 0 || comb.count == k {
return
}
for i in nextStart..<9 {
comb.append(i + 1)
backtrack(remain - i - 1, k, &comb, i + 1, &results)
comb.removeLast()
}
}
func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
var results = [[Int]]()
var comb = [Int]()
backtrack(n, k, &comb, 0, &results)
return results
}
}Ставь 👍 и забирай 📚 Базу знаний