Factor Combinations - Practice Coding Problems

Factor Combinations - Problem

Backtracking Medium

Numbers can be regarded as the product of their factors. For example, 8 = 2 × 2 × 2 = 2 × 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note: The factors should be in the range [2, n - 1].

Input & Output

Example 1 — Basic Case

$ Input: n = 12

› Output: [[2,6],[2,2,3],[3,4]]

💡 Note: 12 can be factored as 2×6, 2×2×3, or 3×4. All factors must be in range [2, 11]

Example 2 — Single Factor Pair

$ Input: n = 8

› Output: [[2,4],[2,2,2]]

💡 Note: 8 can be factored as 2×4 or 2×2×2

Example 3 — Prime Number

$ Input: n = 37

› Output: []

💡 Note: 37 is prime, so it has no factors in range [2, 36]

Constraints

1 ≤ n ≤ 10⁷
Factors must be in range [2, n-1]

Visualization

Tap to expand

Understanding the Visualization

Input

Given number n = 12

Process

Find all ways to multiply factors to get 12

Output

Return all valid factor combinations

Key Takeaway

🎯 Key Insight: Use backtracking to systematically explore all valid factor combinations while avoiding duplicates

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use backtracking to systematically explore all factor combinations while avoiding duplicates. Best approach is optimized backtracking which only checks factors up to sqrt(n) and maintains sorted order. Time: O(2^k), Space: O(k) where k is the number of factors.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(2^n)	Generate all possible factor combinations without optimization
Optimized Backtracking	O(2^k)	O(k)	Use backtracking with pruning to efficiently find all factor combinations

Brute Force Recursion — Algorithm Steps

Start with factors from 2 to sqrt(n)
For each factor, recursively find factors of quotient
Collect all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n=12, try factors 2,3,4...

Recurse

For each factor, find factors of quotient

Collect

Gather all valid combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int** result;
int* resultSizes;
int resultSize;
int resultCapacity;

void backtrack(int num, int start, int* current, int currentSize) {
    if (num == 1) {
        if (currentSize > 1) {
            if (resultSize >= resultCapacity) {
                resultCapacity *= 2;
                result = realloc(result, sizeof(int*) * resultCapacity);
                resultSizes = realloc(resultSizes, sizeof(int) * resultCapacity);
            }
            result[resultSize] = malloc(sizeof(int) * currentSize);
            memcpy(result[resultSize], current, sizeof(int) * currentSize);
            resultSizes[resultSize] = currentSize;
            resultSize++;
        }
        return;
    }
    
    for (int i = start; i <= (int)sqrt(num); i++) {
        if (num % i == 0) {
            current[currentSize] = i;
            backtrack(num / i, i, current, currentSize + 1);
        }
    }
    
    if (num >= start) {
        current[currentSize] = num;
        backtrack(1, num, current, currentSize + 1);
    }
}

int** solution(int n, int* returnSize, int** returnColumnSizes) {
    resultCapacity = 100;
    result = malloc(sizeof(int*) * resultCapacity);
    resultSizes = malloc(sizeof(int) * resultCapacity);
    resultSize = 0;
    
    if (n <= 3) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    
    int current[32];
    backtrack(n, 2, current, 0);
    
    *returnSize = resultSize;
    *returnColumnSizes = resultSizes;
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    int* returnColumnSizes;
    int** res = solution(n, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", res[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explores all possible factor combinations exponentially

⚠ Quadratic Growth

Space Complexity

O(2^n)

Recursion stack depth and storing all combinations

⚠ Quadratic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler