problemmediumalgorithmsprint-all-factors-of-a-given-numberprint all factors of a given numberprintallfactorsofagivennumber

Find all unique combinations of factors for given number

MediumUpdated: Jul 31, 2025

Problem

Given a positive number. Find all unique combinations of factors that constitute the number.

Examples

Example 1:

Input: 12
Output: [[1, 12], [2, 6], [2, 2, 3], [3, 4]]
Explanation: 
 - 1 * 12 = 12
 - 2 * 6 = 12
 - 2 * 2 * 3 = 12
 - 3 * 4 = 12

Example 2:

Input: 16
Output: [[1, 16], [2, 8], [2, 2, 4], [2, 2, 2, 2], [4, 4]]
Explanation: 
 - 1 * 16 = 16
 - 2 * 8 = 16
 - 2 * 2 * 4 = 16
 - 2 * 2 * 2 * 2 = 16
 - 4 * 4 = 16

Similar Problem

[Find all prime factors of given number](find-all-prime-factors-of-given-number)

Solution

Method 1 - Backtracking

To find all the unique combinations of factors, we need to use a backtracking approach. We start from 1 and other possible factors, and recursively build combinations until the product equals the given number. Note that we are not asked for only prime factors but any factors, including primes.

Here is the approach:

  • Note that for any number n, the number n itself is a factor which can constitute n by n * 1.
  • Next, we should try to factorize using 2. So, naturally, we will try to completely divide the number n by 2 and get the factors for n/2 to get final factorization. Then try to divide with 3 and get factorization of n/3 and so on.

Using the below recurrence relation, the problem can be solved using a backtracking approach:

fact(n) = n * 1
fact(n) = fact(n/factor) * factor, for factor = 2, 3, 4, ...,n-1

We can easily implement this recurrence relation using recursion. Below is a simple implementation of the above relation.

Code

Java
public class FactorCombinations {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), n, 1);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int start) {
        if (n <= 1) {
            if (tempList.size() > 1) {
                result.add(new ArrayList<>(tempList));
            }
            return;
        }

        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                tempList.add(i);
                backtrack(result, tempList, n / i, i);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        FactorCombinations solution = new FactorCombinations();
        System.out.println(solution.getFactors(12));
        System.out.println(solution.getFactors(16));
        System.out.println(solution.getFactors(15));
    }
}
Python
class FactorCombinations:
    def get_factors(self, n):
        def backtrack(start, n, path, res):
            if n == 1:
                if len(path) > 1:
                    res.append(path[:])
                return
            for i in range(start, n + 1):
                if n % i == 0:
                    path.append(i)
                    backtrack(i, n // i, path, res)
                    path.pop()

        result = []
        backtrack(1, n, [], result)
        return result

# Example usage
fc = FactorCombinations()
print(fc.get_factors(12))  # Output: [[1, 12], [2, 6], [2, 2, 3], [3, 4]]
print(fc.get_factors(16))  # Output: [[1, 16], [2, 8], [2, 2, 4], [2, 2, 2, 2], [4, 4]]
print(fc.get_factors(15))  # Output: [[1, 15], [3, 5]]

Complexity

  • ⏰ Time complexity: O(2^N), where N is the number of factors of the original number. This is because we are recursively exploring combinations of factors, which can lead to an exponential number of possibilities in the worst case.
  • 🧺 Space complexity: O(N), where N is the depth of the recursion tree. This is because the depth of the recursion stack can go as deep as the factorization of the number.

Comments