Сложность: 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 {
backtracking(factors, ans) {
if (factors.length > 1) {
ans.push([...factors]);
}
const lastFactor = factors.pop();
const start = factors.length === 0 ? 2 : factors[factors.length - 1];
for (let i = start; i * i <= lastFactor; ++i) {
if (lastFactor % i === 0) {
factors.push(i, lastFactor / i);
this.backtracking(factors, ans);
factors.pop();
factors.pop();
}
}
factors.push(lastFactor);
}
getFactors(n) {
const ans = [];
this.backtracking([n], ans);
return ans;
}
}Ставь 👍 и забирай 📚 Базу знаний