LC: 254. Factor Combinations
https://leetcode.com/problems/factor-combinations/
254. Factor Combinations
Numbers can be regarded as the product of their factors.
For example,
8 = 2 x 2 x 2 = 2 x 4.
Given an integer n, return all possible combinations of its factors. You may return the answer in any order.
Note that the factors should be in the range [2, n - 1].
Example 1:
Input: n = 1
Output: []Example 2:
Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]Example 3:
Input: n = 37
Output: []Example 4:
Input: n = 32
Output: [[2,16],[4,8],[2,2,8],[2,4,4],[2,2,2,4],[2,2,2,2,2]]The Essence:
Der Problemlöser soll bemerken, dass diese Faktorisierung Rekursion impliziert. Um 48 zu faktorisieren, muss man z.B. auch 24, 12, 6 faktorisieren.
Hier soll der Problemlöser erkennen, was nicht zu machen ist:
Die Teiler enthalten das Paar (Eingabezahl, 1) nicht.
Die Teiler kommen nicht zweifach vor. Für 27 kann z.B. nur ein Paar aus (3, 9) und (9,3) vorkommen.
Details:
Hier kann man die Backtracking-Technik verwenden. Der Basisfälle des Backtrackings sind Primzahlen. Die verarbeiteten Zahlen kann man in einem Stapel speichern, da man sie benötigt wird: Wenn man 24 durch 2 dividiert und die Zahl 12 verarbeitet, dann multipliziert man die Teiler 2 mit den Teilern von 12, um die Teiler von 24 zu erhalten.
Solution(s) and Further Explanation:
Default Code:
Last updated