Factor Combinations

Given a positive integer n, find all possible combinations of its factors. A factor combination is a list of integers that multiply together to equal n, where each integer is greater than 1 and less than n. This problem is useful for understanding number theory concepts like prime factorization and for exploring combinatorial algorithms.

Problem Description

You are tasked with writing a function that takes a positive integer n and returns a list of all distinct combinations of its factors. A factor f of n is an integer such that n % f == 0.

Key Requirements:

• Each factor in a combination must be greater than 1.
• Each factor in a combination must be strictly less than n.
• The order of factors within a combination does not matter (e.g., [2, 3] is the same as [3, 2]). Therefore, ensure that your output only contains unique combinations.
• The output should be a list of lists, where each inner list represents a valid factor combination.

Expected Behavior:

For a given input n, the function should systematically explore all possible ways to break n down into a product of numbers greater than 1 and less than n.

Edge Cases to Consider:

• What happens if n is a prime number?
• What happens if n is small (e.g., 1, 2, 3)?
• The problem statement implies n is a positive integer.

Examples

Example 1:

Input: 12
Output: [[2, 6], [3, 4], [2, 2, 3]]
Explanation:
- 2 * 6 = 12
- 3 * 4 = 12
- 2 * 2 * 3 = 12
Note that [6, 2] is not included as it's a permutation of [2, 6]. [12] is not included as factors must be less than n.

Example 2:

Input: 1
Output: []
Explanation: No factors greater than 1 and less than 1 exist for the number 1.

Example 3:

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

Constraints

• 1 <= n <= 10000
• The input n will always be a positive integer.
• The number of combinations might grow, but the constraints on n should prevent excessive computation time. Aim for a solution that can find all combinations within a reasonable time frame for the given n.

Notes

This problem can be approached using recursion or backtracking. When generating combinations, consider starting with the smallest possible factor and recursively finding combinations for the remaining quotient. To avoid duplicate combinations and ensure factors are in non-decreasing order, you can enforce that the current factor being considered must be greater than or equal to the previous factor added to the combination.