Factor Combinations

Problem: Factor Combinations

It's easy to solve this problem by backtracking. What we care about is how to return the answer as early as we can. There are 2 things we can do about it. First, it's easy to figure out using square to ensure the answer in order and check fewer situations. Second, when we are dealing with factor 4, we don't need to deal with factor 2, which means we shall start finding factors properly.

Code in Python:

class Solution(object):
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        ans = []
        def _getFactors(start, x, factors):
            for i in xrange(start, int(x**0.5)+1):
                if x % i == 0:
                    if x / i == 1: ans.append(factors+[i])
                    else:
                        ans.append(factors + [i, x/i])
                        _getFactors(i, x / i, factors+[i])
        _getFactors(2, n, [])
        return ans