Factor combinations

Backtracking

50.5% acceptance

Mar 31, 2026

1179

Numbers can be regarded as the product of their factors. For example, 8 = 2 x 2 x 2 = 2 x 4. Given an integer n, return all possible combinations of its factors. You may return the answer in any order. Note that the factors should be in the range [2, n - 1].

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_factors(n: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    Self::backtrack(n, 2, &mut path, &mut result);
    result
  }

  fn backtrack(n: i32, start: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    let mut i = start;
    while i * i <= n {
      if n % i == 0 {
        path.push(i);
        path.push(n / i);
        result.push(path.clone());
        path.pop();
        Self::backtrack(n / i, i, path, result);
        path.pop();
      }
      i += 1;
    }
  }
}