Algorithms to Compute the Factor Combinations for An Integer using DFS and BFS

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: You may assume that n is always positive. Factors should be greater than 1 and less than n.

Example 1:
Input: 1
Output: []

Example 2:
Input: 37
Output:[]

Example 3:
Input: 12
Output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:
Input: 32
Output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Relevant Tool: Integer Factorization to Prime Factors with API

Integer Factor Combination via Depth First Search Algorithm

We can use the DFS (Depth First Search) Algorithm to Backtrack the integer factors. If we find a current factor (no less than its previous factor) e.g. i, we can recursively call the dfs function with n/i. The terminating condition is when n becomes 1, then we find a factor combination.

The 1 and n should be both excluded as they are not the factors. And we can avoid the duplicate combination by always searching for a factor that is not less than its previous one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        dfs(n, {});        
        // remove the [n] factor
        if (!r.empty()) r.erase(end(r), end(r) + 1);
        return r;
    }
private:
    void dfs(int n, vector<int> cur) {
        if (n == 1) {
            if (!cur.empty()) r.push_back(cur);
            return;
        }
        int k = 2;
        if (!cur.empty()) {
            k = max(k, cur.back());
        }
        for (int i = k; i <= n; ++ i) {
            if ((n % i) == 0) { // current is a factor
                cur.push_back(i);
                dfs(n / i, cur); 
                cur.pop_back();
            }
        }
    }
    vector<vector<int>> r;
};

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        dfs(n, {});        
        // remove the [n] factor
        if (!r.empty()) r.erase(end(r), end(r) + 1);
        return r;
    }
private:
    void dfs(int n, vector<int> cur) {
        if (n == 1) {
            if (!cur.empty()) r.push_back(cur);
            return;
        }
        int k = 2;
        if (!cur.empty()) {
            k = max(k, cur.back());
        }
        for (int i = k; i <= n; ++ i) {
            if ((n % i) == 0) { // current is a factor
                cur.push_back(i);
                dfs(n / i, cur); 
                cur.pop_back();
            }
        }
    }
    vector<vector<int>> r;
};

Integer Factor Combinatoin via Breadth First Search Algorithm

The same backtracking algorithm can be implemented using Breadth First Search (BFS) approach. Each node in the queue is a key-value pair where key is the current number to factorize and the value is its previous combination.

Unless the current factor will be the last one, we push its children nodes to the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        queue<pair<int, vector<int>>> Q;
        Q.push({n, {}});
        vector<vector<int>> r;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            int k = 2;
            if (!p.second.empty()) {
                k = max(k, p.second.back());
            }
            for (int i = k; i <= p.first; ++ i) {
                if (p.first % i == 0) {
                    vector<int> next(p.second);
                    next.push_back(i);
                    if (p.first / i == 1) { // the last factor
                        if (next[0] != n) {
                            r.push_back(next);
                        }
                    } else {
                        Q.push({p.first / i, next});
                    }
                }
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        queue<pair<int, vector<int>>> Q;
        Q.push({n, {}});
        vector<vector<int>> r;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            int k = 2;
            if (!p.second.empty()) {
                k = max(k, p.second.back());
            }
            for (int i = k; i <= p.first; ++ i) {
                if (p.first % i == 0) {
                    vector<int> next(p.second);
                    next.push_back(i);
                    if (p.first / i == 1) { // the last factor
                        if (next[0] != n) {
                            r.push_back(next);
                        }
                    } else {
                        Q.push({p.first / i, next});
                    }
                }
            }
        }
        return r;
    }
};

Both approaches will need to complete the search to find all possible factor combination. The BFS is iterative and thus free of stack-over-flow risk that the Recursive DFS may have.

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) —