Factor Combinations

medium backtracking math

Problem

Numbers can be regarded as the product of their factors. Return all unique combinations of factors of n (each factor ≥ 2 and the combination excludes n itself).

Inputn = 12

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

12 = 2·6 = 2·2·3 = 3·4 (4·3 is the same combo and gets pruned by the ascending-start rule).

def get_factors(n):
    res = []
    def back(start, remain, path):
        i = start
        while i * i <= remain:
            if remain % i == 0:
                res.append(path + [i, remain // i])
                back(i, remain // i, path + [i])
            i += 1
    back(2, n, [])
    return res

function getFactors(n) {
  const res = [];
  function back(start, remain, path) {
    for (let i = start; i * i <= remain; i++) {
      if (remain % i === 0) {
        res.push([...path, i, remain / i]);
        back(i, remain / i, [...path, i]);
      }
    }
  }
  back(2, n, []);
  return res;
}

class Solution {
    List> res = new ArrayList<>();
    public List> getFactors(int n) {
        back(2, n, new ArrayList<>()); return res;
    }
    void back(int start, int remain, List path) {
        for (int i = start; i * i <= remain; i++) {
            if (remain % i == 0) {
                List c = new ArrayList<>(path); c.add(i); c.add(remain / i);
                res.add(c);
                path.add(i); back(i, remain / i, path); path.remove(path.size() - 1);
            }
        }
    }
}

class Solution {
    vector> res;
    void back(int start, int remain, vector& path) {
        for (int i = start; i * i <= remain; i++) {
            if (remain % i == 0) {
                auto c = path; c.push_back(i); c.push_back(remain / i);
                res.push_back(c);
                path.push_back(i); back(i, remain / i, path); path.pop_back();
            }
        }
    }
public:
    vector> getFactors(int n) { vector p; back(2, n, p); return res; }
};

Explanation

We want every way to write n as a product of factors that are all 2 or larger, excluding n by itself. To avoid listing the same product in different orders, we only ever pick factors in non-decreasing order.

The function back(start, remain, path) looks for the next factor of remain, trying i from start upward. start guarantees the new factor is at least as big as the previous one, so 3·4 is found but 4·3 is not.

When i divides remain, two things happen. We immediately record path + [i, remain // i], treating remain // i as the final factor. We also recurse into back(i, remain // i, path + [i]) to keep breaking that quotient down further.

The loop only runs while i * i <= remain. Past the square root, the quotient would be smaller than i, which would break the non-decreasing rule and just repeat earlier results, so we stop.

Example: n = 12. With i = 2 we record [2,6] and recurse on 6, which gives [2,2,3]. With i = 3 we record [3,4]. That's the full answer [[2,6],[2,2,3],[3,4]].

Time: O(n^{log log n}) (output-sensitive) Space: O(log n) recursion