254. Factor Combinations

[altay9]

https://leetcode.com/problems/factor-combinations

Burada "factor" dediği, bir sayının çarpanları demektir.
8 = 2 x 2 x 2 şeklinde yazılabilirdi.
= 2 x 4 şeklinde de yazılabilirdi. Dolayısı ile, 8'in çarpan kombinasyonlarına bu ikisi de dahildir.

Varsayılan kod:

class Solution {
    public List<List<Integer>> getFactors(int n) {
        
    }
}

Burada bizden, bir sayının tüm çarpan kombinasyonları isteniyor.

[ErdemT09]

İnternette buna bulduğum çözümler neredeyse brute-force'umsu bir biçimde sayıya veya köküne kadar tüm sayılarla bölünmesine bakıyorlar. Acaba bunun yerine sayının asal çarpanlarını bulup onları sayıp saymama durumuna göre #43 'deki gibi bir backtraking'le çözmek daha verimli olabilir mi?

[altay9]

Tabii, neden olmasın? Deneriz.

[ErdemT09]

Asal çarpanlarına ayırıp yapmak ya çok verimsiz ya da karmaşık bir şeye yol açabiliyor, öbür çözümlere bakılmalı. En azından artık burada asal çarpanlarına ayırma algoritması var.