Ac solution code


  • 0

    Special thanks to yinfeng.zhang.9

    The basic idea is using DFS to get the combination of the number's factors.

    Time complexity = O(n!)

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        DFS(n, 2, new LinkedList<Integer>(), res);
        return res; 
    }    
    void DFS(int n, int start, List<Integer> curList, List<List<Integer>> res) {
        if (n <= 1) {
            if (curList.size() > 1) // <-Excludes the original n
                res.add(new LinkedList<Integer>(curList));
            return;
        } 
        for (int i = start; i <= n; i++) {
            if (n % i == 0) {// One factor
                curList.add(i);
                DFS(n / i, i, curList, res);
                curList.remove(curList.size() - 1);
            }
        }
    }  
    

  • 0
    C

    Elegant solution , thanks man.


Log in to reply
 

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