Alternative Python solution


  • 2
    Z

    Run time is 40 ~ 52 ms, competitive to other methods

    Key is: the output combination is in ascending order, so when we find a factor, the next factor (in next recursion) has to >= current factor

    Then we can do the dfs search:

    def getFactors(self, n):        
        res = []
        self.helper(n, 2, res, [])
        return res[:-1] # the last factor is n itself
        
    def helper(self, n, bound, res, temp):
        if n == 1:
            res.append(temp)
            return
        for fac in range(bound, int(n**0.5)+1):
            if n%fac == 0:
                self.helper(n/fac, fac, res, temp+[fac])
        self.helper(1, n, res, temp+[n]) # allow itself to be a factor as well

Log in to reply
 

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