LeetCode 254: Factor Combinations Solution in Python – A Step-by-Step Guide

What Is LeetCode 254: Factor Combinations?

In LeetCode 254: Factor Combinations, you’re given an integer n, and your task is to return a list of all possible combinations of factors that multiply to n. Each combination is a list of integers greater than 1, and the order within each combination doesn’t matter (though the problem typically expects factors in ascending order). This problem is a fun twist on number theory, related to challenges like LeetCode 204: Count Primes, but focuses on generating combinations rather than counting.

Problem Statement

• Input: An integer n.
• Output: A list of lists, where each sublist contains factors that multiply to n.
• Rules: Factors must be greater than 1; include all valid combinations; n itself is not a factor unless it’s the only factor (e.g., for primes).

Constraints

• n: 1 to 10^6.

Examples

• Input: n = 12
• Output: [[2,6], [3,4], [2,2,3]]
• Input: n = 1
• Output: [] (no factors > 1).
• Input: n = 8
• Output: [[2,4], [2,2,2]]
• Input: n = 7
• Output: [] (prime, no factor pairs).

Understanding the Problem: Finding Factor Groups

To solve LeetCode 254: Factor Combinations in Python, we need to find all ways to express n as a product of integers greater than 1. For example, 12 can be 2 * 6, 3 * 4, or 2 * 2 * 3. A naive approach—trying every possible number combination—is too slow. We’ll use two methods: 1. Best Solution (Backtracking with Pruning): O(2^√n) time—fast and smart. 2. Alternative Solution (Brute Force Generation): O(n * 2^n) time—simple but inefficient.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Backtracking with Pruning

Why This Is the Best Solution

The backtracking with pruning approach is the top choice for LeetCode 254 because it efficiently explores factor combinations in O(2^√n) time by building them step-by-step and cutting off useless paths early. It’s beginner-friendly once explained, uses minimal space, and scales well, making it the ideal solution.

How It Works

Think of this solution as building a multiplication puzzle: you start with n and try to break it into smaller pieces (factors), one at a time, until you’ve used it all up. You only keep going down paths that make sense, skipping ones that won’t work. Here’s how it works, step-by-step, explained simply for beginners:

• Step 1: Start with the Target:
• You have n (e.g., 12), and you want to find all ways to split it into factors like [2, 6] or [3, 4].
• Step 2: Use Backtracking:
• Backtracking is like trying different puzzle pieces:
• Pick a factor (e.g., 2 for 12).
• Divide n by that factor (12 / 2 = 6).
• Now work with the remaining number (6) and find its factors.
• Keep a list of factors you’ve picked (e.g., [2]).
• When the remaining number is a factor > 1, add it to the list (e.g., [2, 6]).
• If you hit 1, you’ve got a valid combination—save it!
• Step 3: Try Factors Smartly:
• Only try factors from 2 up to √n (square root of n), because bigger factors pair with smaller ones you’ve already tried.
• For 12, try 2 (12/2 = 6), 3 (12/3 = 4)—no need for 4 or 6 yet, they’ll come up later.
• Step 4: Prune Useless Paths:
• If a factor doesn’t divide evenly (e.g., 5 for 12), skip it.
• Only include factors ≥ the last one you used (to avoid duplicates like [2, 3] and [3, 2]).
• Step 5: Build Combinations:
• Use a helper function to recursively try factors, adding valid combinations to a result list.

It’s like solving a maze: you try a path (a factor), see if it works, and backtrack if it doesn’t, keeping only the paths that reach the goal!

Step-by-Step Example

Example: n = 12

• Setup: Start with n = 12, result = [], current factors = [].
• Try Factors from 2:
• Factor 2:
• 12 / 2 = 6 (remainder 0, good).
• Current = [2], remaining = 6.
• Try factors for 6 (from 2, since ≥ last factor 2):
• Factor 2: 6 / 2 = 3, Current = [2, 2], remaining = 3.
• Try 3: 3 / 3 = 1, Current = [2, 2, 3], remaining = 1 (done).
• Add [2, 2, 3] to result.
• Factor 3: 6 / 3 = 2, Current = [2, 3], remaining = 2.
• 2 < 3, skip (keep order).
• Factor 6: 6 / 6 = 1, Current = [2, 6], remaining = 1 (done).
• Add [2, 6] to result.
• Factor 3:
• 12 / 3 = 4.
• Current = [3], remaining = 4.
• Try factors for 4 (from 3):
• Factor 4: 4 / 4 = 1, Current = [3, 4], remaining = 1.
• Add [3, 4] to result.
• Result: [[2,6], [2,2,3], [3,4]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        # Step 1: Handle edge cases
        if n <= 1:
            return []  # No factors > 1 possible

        # Step 2: Result list to store combinations
        result = []

        # Step 3: Helper function for backtracking
        def backtrack(remaining, start_factor, current):
            # If remaining is 1, we’ve used up n
            if remaining == 1 and len(current) > 0:
                result.append(current[:])  # Add a copy of current factors
                return

            # Try factors from start_factor up to sqrt(remaining)
            for i in range(start_factor, int(remaining ** 0.5) + 1):
                # Step 4: Check if i is a factor
                if remaining % i == 0:
                    # Add i to current combination
                    current.append(i)
                    # Recurse with remaining / i, starting from i
                    backtrack(remaining // i, i, current)
                    # Backtrack by removing i
                    current.pop()

            # Step 5: If remaining itself is a factor > start_factor
            if remaining >= start_factor:
                current.append(remaining)
                result.append(current[:])
                current.pop()

        # Step 6: Start backtracking with n and 2
        backtrack(n, 2, [])
        return result

• Time Complexity: O(2^√n)—exponential, but pruned to factors up to √n.
• Space Complexity: O(√n)—recursion depth and current list.

This solution is like a clever puzzle solver—trying pieces that fit and skipping ones that don’t!

Alternative Solution: Brute Force Generation

Why an Alternative Approach?

The brute force generation approach tries all possible factor combinations by finding all factors first, then building combinations. It’s slower but shows the problem’s raw mechanics, making it a good starting point for beginners.

How It Works

Imagine listing every factor of n, then mixing and matching them to see which groups multiply to n. Here’s how it works, explained simply:

• Step 1: Find All Factors:
• Get every number > 1 that divides n (e.g., for 12: 2, 3, 4, 6, 12).
• Step 2: Generate Combinations:
• Try all subsets of these factors, checking if their product equals n.
• Step 3: Filter Valid Ones:
• Keep only those that work, removing duplicates.

It’s like picking candies from a jar and checking if they add up to your total—slow but thorough!

Step-by-Step Example

Example: n = 12

• Factors: 2, 3, 4, 6, 12.
• Combinations:
• [2, 6]: 2 * 6 = 12, valid.
• [3, 4]: 3 * 4 = 12, valid.
• [2, 2, 3]: 2 * 2 * 3 = 12, valid.
• [12]: Not typically included, but 12 = 12.
• Result: [[2,6], [3,4], [2,2,3]] (excluding [12] per convention).

Code for Brute Force Approach

class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
        # Step 1: Handle edge cases
        if n <= 1:
            return []

        # Step 2: Find all factors
        factors = []
        for i in range(2, n + 1):
            if n % i == 0:
                factors.append(i)

        # Step 3: Generate combinations
        result = []
        def generate(curr, index, target):
            if target == 1 and len(curr) > 0:
                result.append(curr[:])
                return
            if target < 1 or index >= len(factors):
                return
            # Skip this factor
            generate(curr, index + 1, target)
            # Include this factor
            if target % factors[index] == 0:
                curr.append(factors[index])
                generate(curr, index, target // factors[index])
                curr.pop()

        generate([], 0, n)
        return result

• Time Complexity: O(n * 2^n)—checking all subsets.
• Space Complexity: O(n)—factor list and recursion.

It’s exhaustive but slow.

Comparing the Two Solutions

• Best Solution (Backtracking):
• Pros: O(2^√n) time, efficient, scalable.
• Cons: Requires backtracking concept.
• Alternative Solution (Brute Force):
• Pros: Simple factor listing.
• Cons: O(n * 2^n) time, inefficient.

Backtracking wins for speed.

Additional Examples and Edge Cases

Prime Number

• n = 7 → []

Single Factor

• n = 4 → [[2,2]]

Large Number

• n = 32 → [[2,16], [4,8], [2,2,8], [2,4,4], [2,2,2,4], [2,2,2,2,2]]

Both handle these well.

Complexity Breakdown

• Backtracking:
• Time: O(2^√n)—pruned exploration.
• Space: O(√n)—stack.
• Brute Force:
• Time: O(n * 2^n)—all combinations.
• Space: O(n)—factors.

Backtracking is faster.

Key Takeaways for Beginners

• Backtracking: Build step-by-step, undo if needed.
• Pruning: Skip bad paths early.
• Brute Force: Try everything—good for learning.
• Python Tip: Loops and recursion mix well—see [Python Basics](/python/basics).

Final Thoughts: Factor Like a Pro

LeetCode 254: Factor Combinations in Python is a fun factorization challenge. The backtracking solution offers efficiency, while brute force provides clarity. Want more? Try LeetCode 204: Count Primes or LeetCode 343: Integer Break. Ready to factor? Head to Solve LeetCode 254 on LeetCode and break down those numbers today!