LeetCode 254. Factor Combinations（因式分解）

原题网址：https://leetcode.com/problems/factor-combinations/

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.
      

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is 

   [2, 6]

   , not 

   [6, 2]

   .
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 

input: 

1

output: 

[]
      

input: 

37

output: 

[]
      

input: 

12

output:

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

input: 

32

output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]      

思路：深度优先搜索。

public class Solution {
    private void find(List<Integer> factors, int target, List<List<Integer>> results) {
        // System.out.printf("factors=%s\n", factors);
        if (target == 1) {
            if (!factors.isEmpty()) {
                List<Integer> result = new ArrayList<>(factors.size());
                result.addAll(factors);
                results.add(result);
            }
            return;
        }
        int min = factors.isEmpty()? 2 : factors.get(factors.size()-1);
        int max = factors.isEmpty()? target/2 : target;
        for(int f = min; f <= max; f ++) {
            if (target % f != 0) continue;
            factors.add(f);
            find(factors, target/f, results);
            factors.remove(factors.size()-1);
        }
    }
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> results = new ArrayList<>();
        find(new ArrayList<>(), n, results);
        return results;
    }
}
           

优化：关键在于i*i<=n，可以大幅提升性能。

public class Solution {
    private void find(int from, int n, List<Integer> factors, List<List<Integer>> results) {
        for(int i=from; i*i<=n; i++) {
            if (n % i == 0) {
                factors.add(i);
                find(i, n/i, factors, results);
                factors.remove(factors.size()-1);
            }
        }
        if (!factors.isEmpty()) {
            factors.add(n);
            results.add(new ArrayList<>(factors));
            factors.remove(factors.size()-1);
        }
    }
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> results = new ArrayList<>();
        find(2, n, new ArrayList<>(), results);
        return results;
    }
}
           

由于ArrayList较慢，如果固定分配空间可以进一步提升性能。

public class Solution {
    private void find(int from, int n, int[] factors, int len, List<List<Integer>> results) {
        for(int i=from; i*i<=n; i++) {
            if (n % i == 0) {
                factors[len] = i;
                find(i, n/i, factors, len+1, results);
            }
        }
        if (len > 0) {
            factors[len] = n;
            Integer[] f = new Integer[len+1];
            for(int i=0; i<=len; i++) f[i] = factors[i];
            results.add(Arrays.asList(f));
        }
    }
    public List<List<Integer>> getFactors(int n) {
        int p = 0;
        for(int i=1; i<=n; p++, i*=2);
        List<List<Integer>> results = new ArrayList<>();
        find(2, n, new int[p], 0, results);
        return results;
    }
}