Teaching Kids Programming – Backtracking Algorithm to Find Factor Combinations (Math, Recursive Depth First Search)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Numbers can be regarded as the product of their factors. For example, 8 = 2 x 2 x 2 = 2 x 4. Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n – 1].

Example 1:
Input: n = 1
Output: []

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

Example 3:
Input: n = 37
Output: []

Constraints:
1 <= n <= 10^7

Backtracking Algorithm to Find Factor Combinations (Math, Recursive Depth First Search)

Prime numbers do not have factors that range from 2 to n-1 thus we should return empty list for prime numbers. Similar to checking prime number factors, we only need to check possible factors up to square root of N – because we have i and N//i as a pair of factors.

To avoid duplications we keep tracking of the last added factor, so that the factors are strictly non-ascending. We need to restore the list after the recursive depth first search algorithm aka backtracking. When we have factor i, the remaining is n//i, and we need to update the list accordingly. The next factor to consider should be no less than i, in order to avoid duplicate combinations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
        
        def dfs(n, s, c):
            for i in range(s, int(n**0.5) + 1):
                if n % i == 0:
                    c += [i]
                    ans.append(c[:] + [n // i])
                    dfs(n // i, i, c)
                    c.pop()
        
        dfs(n, 2, [])
        return ans

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
        
        def dfs(n, s, c):
            for i in range(s, int(n**0.5) + 1):
                if n % i == 0:
                    c += [i]
                    ans.append(c[:] + [n // i])
                    dfs(n // i, i, c)
                    c.pop()
        
        dfs(n, 2, [])
        return ans

We can make a copy of the list so that we don’t need to restore it.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
        
        def dfs(n, s, c):
            for i in range(s, int(n**0.5) + 1):
                if n % i == 0:
                    ans.append(c[:] + [i, n // i])
                    dfs(n // i, i, c + [i])
        
        dfs(n, 2, [])
        return ans

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        ans = []
        
        def dfs(n, s, c):
            for i in range(s, int(n**0.5) + 1):
                if n % i == 0:
                    ans.append(c[:] + [i, n // i])
                    dfs(n // i, i, c + [i])
        
        dfs(n, 2, [])
        return ans

Factor Combination Algorithms

• Teaching Kids Programming – Breadth First Search Algorithm to Find Factor Combinations
• Teaching Kids Programming – Backtracking Algorithm to Find Factor Combinations (Math, Recursive Depth First Search)
• Algorithms to Compute the Factor Combinations for an Integer using DFS and BFS

–EOF (The Ultimate Computing & Technology Blog) —