254. 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. You may assume that n is always positive.
2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

M1: find all factors of n first, then use DFS to find find all combinations of factors

1. first find all factors of integer n　　-- time = O(n)

2. use DFS to find all combinations of factors　　-- time = O(2 ^ k), k: # of factors

time = O(n + 2 ^ k), space = O(k)

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> factors = allFactors(n);
        if(factors.size() == 0) {
            return new ArrayList<>();
        }
        dfs(n, 0, factors, new ArrayList<>(), res);
        return res;
    }
    
    public void dfs(int n, int idx, List<Integer> factors, List<Integer> list, List<List<Integer>> res) {
        if(n == 1) {
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i = idx; i < factors.size(); i++) {
            if(factors.get(i) > n) {
                break;
            }
            if(n % factors.get(i) == 0) {
                list.add(factors.get(i));
                dfs(n / factors.get(i), i, factors, list, res);
                list.remove(list.size() - 1);
            }
        }
    }
    
    public List<Integer> allFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for(int i = 2; i < n; i++) {
            if(n % i == 0) {
                factors.add(i);
            }
        }
        return factors;
    }
}

M2: find factors in DFS process

初始状态从2开始一直check到n

在dfs func 里需要一个start参数(去重)，一个remain参数。每层recursion里，check 从 start 到 sqrt(remain)的所有数（剪枝），如果该数可被remain整除，则进入下一层recursion。

剪枝原理：为了保持最后结果的有序，最大只需要检查到sqrt(remain)即可（否则会出现32=2x8x2这样的乱序结果），但是i * i <= remain会漏掉一种情况：remain本身也是factor，所以在最后循环结束后，还要再加上remain并进行一次递归

complexity analysis:

time = (# of nodes in the recursion tree) * (the time each node takes)

# of nodes in the recursion tree = (the largest # of branches among every single node) ^ (the height of the recursion tree)

time: O(sqrt(n) ^ (logn))

There are logn recursion levels because an integer has at most n (from 2 to n) factors, and thus the height of recursion tree is logN (since when the given number n is only decomposed by 2 will lead to the solution which has the longest length (32=2x2x2x2x2))

In each recursion level, there're at most sqrt(n) states we need to consider about (i.e. branches)

space: O(logn)

things cost extra space: # of call stacks = the height of the recursion tree = logn

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