A simple java solution


  • 42
    H
    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);
            }
        }
    }

  • 0
    C

    Fastest so far.... why no upvotes?


  • 0
    Y

    great solution! Math.sqrt() check saves a lot of time. I used to have n/2 check, with 22ms, now I have running time down to 3ms. Thanks!


  • 0
    Y

    feel difficult to understand it, could you please give a more detailed explanation?


  • 0
    R

    THis is DFS solution´╝č


  • 0
    X
       public List<List<Integer>> factorCombination(int n) {
            List<List<Integer>> res = new ArrayList<>();
            helper(n, 1, res, new ArrayList<>());
            return res;
        }
    
       void helper(int n, int start, List<List<Integer>> res, List<Integer> curr) {
            if (start > 1) {
                List<Integer> list = new ArrayList<>(curr);
                list.add(n);
                res.add(list);
            }
            for (int i = Math.max(start, 2); i * i <= n; i++) {
                if (n % i == 0) {
                    curr.add(i);
                    helper(n / i, i, res, curr);
                    curr.remove(curr.size() - 1);
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.