Simple and Short Python Recursive Solution

  • 1

    Only consider factors in the range 2 to int(n**0.5)+1. If i is a factor, add the factor pair [i, n/i] to final solution. Also, find the factor combinations of n/i recursively. To avoid duplicates, maintain the ascending order in each factor combination (if r[0] >= i).

    class Solution(object):
        def getFactors(self, n):
            :type n: int
            :rtype: List[List[int]]
            if n <= 3:
                return []
            res = []
            for i in range(2, int(n**0.5)+1):
                if n % i == 0:
                    res.append([i, n/i])
                    res += [[i] + r for r in self.getFactors(n/i) if r[0] >= i]
            return res

  • 0

    I wonder , whats the time complexity of this code ? Isnt this O(2^n)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.