Simple and Short Python Recursive Solution


  • 1
    W

    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
    R

    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.