Introduction

Finding all factorizations of an integer means generating every multiplicative decomposition greater than one, ignoring ordering duplicates. For example, twelve has decompositions such as 2 x 6 and 2 x 2 x 3. A clean way to generate all results is recursive backtracking with a nondecreasing factor constraint.

Core Sections

Problem definition and constraints

Given an integer n, produce all lists of integers greater than one whose product equals n. To avoid duplicates, enforce nondecreasing order in each list. That means 2 x 6 is valid, but 6 x 2 is skipped because it is the same combination in different order.

For n = 12, expected outputs include:

• 2 x 6
• 3 x 4
• 2 x 2 x 3

Prime numbers yield no nontrivial factorization under this definition.

Backtracking approach

The recursive idea is:

• track remaining value to factor.
• try divisors from a start value up to square root of remaining value.
• when divisor divides evenly, add divisor to current path and recurse on quotient.
• also record the pair of current path plus quotient as one full factorization.

1from math import isqrt
2
3
4def all_factorizations(n: int) -> list[list[int]]:
5    result: list[list[int]] = []
6
7    def dfs(remaining: int, start: int, path: list[int]) -> None:
8        for f in range(start, isqrt(remaining) + 1):
9            if remaining % f != 0:
10                continue
11
12            q = remaining // f
13            result.append(path + [f, q])
14            dfs(q, f, path + [f])
15
16    dfs(n, 2, [])
17    return result
18
19
20if __name__ == "__main__":
21    print(all_factorizations(12))

This produces each unique factorization once, because recursion never tries factors smaller than the previous choice.

Why nondecreasing factors remove duplicates

Without ordering constraints, each combination appears in many permutations. For 2 x 2 x 3, permutations include 2 x 3 x 2 and 3 x 2 x 2. By forcing next factor to be at least current factor, recursion explores only canonical order.

This is a standard trick for combination generation and subset style backtracking.

Complexity discussion

The output size itself can be large, so total runtime is output sensitive. For highly composite numbers, the recursion tree branches frequently. For primes, runtime is small because almost no recursive paths continue.

In practice:

• divisor checks run up to square root of current remainder.
• recursion depth is bounded by logarithm base two of n in the longest chain.
• dominant cost is generating and copying result paths.

Iterative variant sketch

You can build an iterative stack simulation, but recursive code is usually clearer for this combinational search. If stack depth is a concern for very large values, iterative simulation or explicit stack can replace recursion.

# Conceptual structure only
# stack items: (remaining, start, path)
# pop, expand divisors, push children

For typical interview and utility contexts, recursive backtracking remains the preferred implementation.

Enhancements

Common extensions include:

• including trivial factorization with n itself based on business rules.
• limiting maximum number of factors.
• restricting factors to primes only.
• returning factorizations as strings for display.

Each extension can be added by pruning conditions in the DFS function.

Common Pitfalls

• Forgetting to enforce nondecreasing factor order, which causes duplicate permutations. Start each recursive loop from previous factor.
• Iterating divisors up to remaining value instead of square root, causing unnecessary work. Stop at integer square root.
• Missing the direct pair recording step path + [f, q], which loses valid outputs. Record pair before deeper recursion.
• Including factor 1, which creates infinite style expansions and invalid decompositions. Restrict factors to values greater than one.
• Treating runtime as simple polynomial complexity. Generation cost depends heavily on number of produced factorizations.

Summary

• All integer factorizations can be generated with recursive backtracking.
• Use a start factor to keep factors nondecreasing and avoid duplicates.
• Check divisors only up to square root for efficiency.
• Complexity is output sensitive and grows with factor richness of n.
• The approach is easy to extend with pruning and formatting rules.