Factor Combinations

lc 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

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]
]

这个题就是每次选好一个数，然后能不能整出完，有点像combination sum 能重复计算的方法。

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(n == 1) return res;
        List<Integer> list = new ArrayList<Integer>();
        helper(res, list,n, 2);
        return res;
    }

    public void helper(List<List<Integer>> res,List<Integer> list, int n, int start ){

        if(n <= 1){
            if(list.size() > 1){

                res.add(new ArrayList<Integer>(list));
                return;

            }

        }

        /*if(map.containsKey(n)){
            list.addAll(map.get(n));
            res.add(new ArrayList<Integer>(list));
            return;
        }*/
        for(int i = start; i <= n; i++){
            if( n % i != 0) continue;
            list.add(i);
            helper(res, list, n / i, i);
            list.remove(list.size() - 1);
        }
    }
}