Factor Combinations - Leetcode Solution

Problem Description:

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Example 1: Input: n = 1 Output: [] Explanation: There are no factors of 1.

Example 2: Input: n = 12 Output: [[2,6],[3,4],[2,2,3]] Explanation: 12 = 2 * 6 = 3 * 4 = 2 * 2 * 3

Solution:

We can solve this problem using backtracking. We will iterate through all the factors of the number and keep track of the factors we have already used in our current combination using a set. We will keep adding factors to our combination until the product of the factors is equal to n. At that point, we add the combination to our result list. We will backtrack and try out other alternatives if the product doesn't match n. In order to avoid duplicates, we start our iteration from the last factor that was used in the previous combination.

Algorithm:

1. We define a recursive function called backtrack that takes four parameters – the current factor we are considering, the current combination of factors, the product of the current combination, and the result list.
2. If the product of the current combination is equal to n, we add the combination to our result list and return.
3. We iterate through all factors greater than or equal to the current factor and add them to our combination. The product of the current combination is then updated.
4. We make a recursive call to backtrack with the updated combination and product and the next factor as the current factor.
5. Once the recursive call returns, we remove the last factor from our combination to backtrack and try other possible combinations of factors.

Code:

Here is the Python code for the above algorithm:

class Solution: def getFactors(self, n: int) -> List[List[int]]: result = [] self.backtrack(2, [], n, result) return result

def backtrack(self, factor, curr, prod, result):
    if prod == 1:
        result.append(curr[:])
        return
    for i in range(factor, int(math.sqrt(prod))+1):
        if prod % i == 0:
            curr.append(i)
            self.backtrack(i, curr, prod//i, result)
            curr.pop()

1