Alternative Python solution

  • 2

    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:
        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.