Lintcode 652. Factorization

A non-negative numbers can be regarded as product of its factors.
Write a function that takes an integer n and return all possible combinations of its factors.

Example

Example1

Input: 8
Output: [[2,2,2],[2,4]]
Explanation:
8 = 2 x 2 x 2 = 2 x 4

Example2

Input: 1
Output: []

Notice

• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combination.

Solution 1: DFS

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution {     /**      * @param n: An integer      * @return: a list of combination      */     public List<List<Integer>> getFactors(int n) {         // write your code here         List<List<Integer>> ans = new ArrayList<>();                   getFactorsHelper(2, n, new ArrayList<Integer>(), ans);                   return ans;     }           private void getFactorsHelper(int start, int n, List<Integer> curList, List<List<Integer>> ans) {         if (n <= 1) {             if (curList.size() > 1) {                 List<Integer> copy = new ArrayList<>(curList);                 ans.add(copy);             }             return;         }                   for (int i = start; i <= Math.sqrt(n); i++) {             if (n % i != 0) {                 continue;             }                           curList.add(i);             getFactorsHelper(i, n / i, curList, ans);             curList.remove(curList.size() - 1);         }           curList.add(n);         getFactorsHelper(n, 1, curList, ans);         curList.remove(curList.size() - 1);     } }

Solution 2: DFS + Memo

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

public class Solution {     /**      * @param n: An integer      * @return: a list of combination      */     public List<List<Integer>> getFactors(int n) {         // write your code here         Map<Integer, List<List<Integer>>> memo = new HashMap<>();                   List<List<Integer>> ans = getFactorsHelper(2, n, memo);         ans.remove(ans.size() - 1);                   return ans;     }           private List<List<Integer>> getFactorsHelper(int start, int n, Map<Integer, List<List<Integer>>> memo) {         List<List<Integer>> ans = new ArrayList<>();         if (n <= 1) {             return ans;         }                   if (memo.containsKey(n)) {             return memo.get(n);         }                   for (int i = 2; i <= Math.sqrt(n); i++) {             if (n % i != 0) {                 continue;             }                           List<List<Integer>> curList = getFactorsHelper(i, n / i, memo);                           for (List<Integer> list : curList) {                 if (i > list.get(0)) {                     continue;                 }                 List<Integer> copy = new ArrayList<>(list);                 copy.add(0, i);                 ans.add(copy);             }         }                   List<Integer> last = new ArrayList<>();         last.add(n);         ans.add(last);                   memo.put(n, ans);         return ans;     } }