Сложность: medium
Числа можно рассматривать как произведение их множителей.
Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.
Обратите внимание, что множители должны быть в диапазоне [2, n - 1].
Пример:
Input: n = 1
Output: []
👨💻 Алгоритм:
1⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans.
2⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.
3⃣В конце выполнения, ans будет содержать все возможные комбинации множителей числа n.
😎 Решение:
class Solution {
private func backtracking(_ factors: inout [Int], _ ans: inout [[Int]]) {
if factors.count > 1 {
ans.append(factors)
}
let lastFactor = factors.removeLast()
for i in (factors.isEmpty ? 2 : factors.last!)...lastFactor {
if i * i > lastFactor { break }
if lastFactor % i == 0 {
factors.append(i)
factors.append(lastFactor / i)
backtracking(&factors, &ans)
factors.removeLast()
factors.removeLast()
}
}
factors.append(lastFactor)
}
func getFactors(_ n: Int) -> [[Int]] {
var ans: [[Int]] = []
var factors: [Int] = [n]
backtracking(&factors, &ans)
return ans
}
}Ставь 👍 и забирай 📚 Базу знаний