BiruLyu
6/15/2017 - 8:21 AM

254. Factor Combinations(1st).java

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        backtracking(2, n, temp, res);
        return res;
        
     }
     
     private void backtracking(int pre, int left, List<Integer> temp, List<List<Integer>> res) {
         if (left == 1 && temp.size() > 1) {
             res.add(new ArrayList<Integer>(temp));
         }
         for(int i = pre; i <= left; i++) {
             if (left % i == 0) {
                 temp.add(i);
                 backtracking(i, left / i, temp, res);
                 temp.remove(temp.size() - 1);
             }
         }
     } 
}
public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (n <= 3) return result;
    helper(n, -1, result, new ArrayList<Integer>());
    return result; 
    }
    
    public void helper(int n, int lower, List<List<Integer>> result, List<Integer> cur) {
    if (lower != -1) {
        cur.add(n);
        result.add(new ArrayList<Integer>(cur));
        cur.remove(cur.size() - 1);
    }
    int upper = (int) Math.sqrt(n);
    for (int i = Math.max(2, lower); i <= upper; ++i) {
        if (n % i == 0) {
            cur.add(i);
            helper(n / i, i, result, cur);
            cur.remove(cur.size() - 1);
        }
    }
}
}