Solution: Factor Combinations

Problem Statement

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.

Example 1:

Input: n = 8  
Output: [[2, 2, 2], [2, 4]]

Example 2:

Input: n = 20  
Output: [[2, 2, 5], [2, 10], [4, 5]]

Constraints:

2 <= n <= 10<sup>7</sup>

Solution

We can use backtracking to find all the factors of a given number $n$ .

.....

Like the course? Get enrolled and start learning!

ctrl

· 2 years ago

P

pavan

· 3 years ago

Mohammed Dh Abbas

· 2 years ago

from math import sqrt 

class Solution:
  def getFactors(self, n):
    
    def get_number_factors():
      factors = set()
      for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
          factors.add(i)
          factors.add(n / i)
      return list(factors)

    def backtrack(result, path, mpy, factors, index):
      if mpy > n:
        return 
        
      if mpy == n and len(path) > 0:
        result.append(path[:])
        return

      for i in range(index, len(factors)):
        mpy *= factors[i]
        path.append(factors[i])
        backtrack(result, path, mpy, factors, i)
        path.pop()
        mpy /= factors[i]
    
    result = []
    factors = get_number_factors()
    backtrack(result, [], 1, factors, 0)

    return result