My Recursive DFS Java Solution


  • 81
    Y
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(result, new ArrayList<Integer>(), n, 2);
        return result;
    }
    
    public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
        if (n <= 1) {
            if (item.size() > 1) {
                result.add(new ArrayList<Integer>(item));
            }
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            if (n % i == 0) {
                item.add(i);
                helper(result, item, n/i, i);
                item.remove(item.size()-1);
            }
        }
    }

  • 6
    Z

    "for (int i = start; i <= n; ++i)" seems inefficient


  • -2
    Z
    class Solution {
    public:
        // select factors from smaller to larger
        // e.g. 32
        // 1st factor must divide 32, can be: 2, 4, 8(no need to consider, 
        // because next factor must be smaller than 8, so pruning)
        // if we select 2, then
        // 2nd factor must divide 16 and not smaller than 2, can be 4, 8(no need to consider, also pruning)
        // if we select 4, then
        // 3nd factor must divide 4 and not smaller than 4, can be 4,
        // we select 4
        // then we get a combination(2, 4, 4)
        vector<vector<int>> getFactors(int n) {
            vector<vector<int> > ans;
            if(n <= 0){
                return ans;
            }
            
            vector<int> curr;
            bt(n, 2, curr, ans);
            return ans;
        }
        
    private:
        void bt(int n, int minFactor, vector<int> &curr, vector<vector<int> > &ans){
            if(n <= 1){
                if(curr.size() > 1){
                    ans.push_back(curr);
                }
                return;
            }
            
            curr.push_back(n);
            bt(1, n, curr, ans);
            curr.pop_back();
            
            for(int k = minFactor; k*k <= n; ++k){
                if(n%k == 0){
                    curr.push_back(k);
                    bt(n/k, k, curr, ans);
                    curr.pop_back();
                }
            }
        }
    
    };

  • 0
    Y

    I don't see how it is inefficient, each time n is divided by a factor, and we should loop each number from start to the new n.


  • 24
    0

    2 small changes make it much faster, please look my comments for the 2 changes in the code

    public class Solution {
        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>> results = new ArrayList<>();
            if (n <=3) {
                return results;
            }
            
            getFactors(n, 2, new ArrayList<Integer>(), results);
            return results;
        }
        
        private void getFactors(int n, int start, List<Integer> current, List<List<Integer>> results) {
            if (n == 1) {
            	if (current.size() > 1) {
            		results.add(new ArrayList<Integer>(current));
            	}
                return;
            }
    	        
            
            for (int i = start; i <= (int) Math.sqrt(n); i++) {  // ==> here, change 1
                if (n % i != 0) {
                    continue;
                }   
                current.add(i);
                getFactors(n/i, i, current, results);
                current.remove(current.size()-1);
            }
            
            int i = n; // ===> here, change 2
            current.add(i);
            getFactors(n/i, i, current, results);
            current.remove(current.size()-1);
        }
    }

  • -3
    This post is deleted!

  • 0

    Good method bro!


  • 5

    Hey friend, thanks for your inspiration. I benefit a lot from your method. I made a little change to your code and it runs so much faster(only 2 ms). Here it is.

    public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> element = new ArrayList<>();
        helper(list,n,2,element,(int)Math.sqrt(n));
        return list;
    }
    public void helper(List<List<Integer>> list, int n, int start, List<Integer> element,int upper)
    {
        if(n == 1 &&element.size() > 1)
        {
            list.add(new ArrayList<Integer>(element));
            return;
        }
        for(int i = start; i <= n; i++)
        {
            if(i > upper)
            {
                i = n;
            }
            if(n %i == 0)
            {
                element.add(i);
                helper(list,n/i,i,element,(int)Math.sqrt(n/i));
                element.remove(element.size() - 1);
            }
        
        }
        
        
    }
    

    }

    Actually, factors of an integer n (except for 1 and n) are always between 1 and sqrt(n), so you do not have to check those numbers between sqrt(n) and n. However, in your method, we need to check n, so I added a check, when i is greater than sqrt(n), i will jump directly to n. This little change improved a lot. Thank you!


  • 0
    V

    Very good method , real backtracking . Although it could be a bit more efficient , still it's very good


  • 1
    C

    @060601199 Great DFS + backtracking solution. What is the time complexity? O(sqrt(n)* sqrt(sqrt(n))sqrt(sqrt(sqrt(n)))...*1) ~= O(n)?


  • 0
    E

    I am also wondering about the time complexity. I guess the worst case is at least exponential in the number of prime factors?


  • 0
    E

    For example, if you have k distinct prime factors, then the number of result of size 2 is already 2^k. And we also may have result of size larger than 2. But I am not sure how to calculate how much time it costs..


  • 1

    @jedihy I wish I could down vote you but do not have enough reputation


  • 0
    I

    @yinfeng.zhang.9 better?

        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>> ans = new ArrayList<>();
            helper(n, 2, ans, new ArrayList<>());
            return ans;
        }
        void helper(int n, int m, List<List<Integer>> ans, List<Integer> cur) {
            for (int i = m; i <= n/i; ++i) {
                if (n % i > 0) continue;
                List<Integer> sub = new ArrayList<>(cur);
                sub.add(i);
                sub.add(n / i);
                ans.add(sub);
                cur.add(i);
                helper(n / i, i, ans, cur);
                cur.remove(cur.size() - 1);
            };
        }```

  • 0
    S

    Can someone explain why we remove the item after calling helper in the following block:
    if (n % i == 0) {
    item.add(i);
    helper(result, item, n/i, i);
    item.remove(item.size()-1);
    }


  • 1
    A

    @sharm173 That's the part of back track. you have a for loop go from say 2 to 12 right? once you go [2, 2, 3], you get one combination, then you need to go back to the for loop to try the larger numbers, so you need to remove the newly added numbers so you will be able to try 2 3 and 2 4 and 2 5 until you find [2, 6] which is another combination.


  • 0
    F

    @zhengjiusi it is fine, actually if you notice start <= n, so for start > sqrt(n), next search in helper will directly return.


  • 1
    Y

    Similar idea, but use i * i <= n as condition instead. Its running time is 1ms.

    public class Solution {
        List<List<Integer>> ans = new ArrayList<>();
    
        public void getFactors(int n, int s, List<Integer> path) {
            for (int i = s; i * i <= n; ++i) {
                if (n % i == 0) {
                    path.add(i);
                    getFactors(n / i, i, path);
                    path.add(n / i);
                    ans.add(new ArrayList<>(path));
                    path.remove(path.size() - 1);
                    path.remove(path.size() - 1);
                }
            }
        }
    
        public List<List<Integer>> getFactors(int n) {
            getFactors(n, 2, new ArrayList<>());
            return ans;
        }
    }
    

  • 0
    Z

    Can anyone explain why in the for loop, we stop at the i*i<=n?

    for (int i = start; i * i <= n; ++i){}


  • 0

    I think the main problem of this question is avoid duplication.
    When the recursive call goes deeper, the numerator d gets larger.

        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>>  res = new ArrayList<List<Integer>>();
            helper(res, new ArrayList<Integer>(), n, 2);
            return res;
        }
        
        void helper(List<List<Integer>> res, List<Integer> list, int n, int d){
           for(int i = d;  i <= Math.sqrt(n); i++){
             if(n % i != 0) continue;
             int x = n / i;
             list.add(i);
             list.add(x);
             res.add(new ArrayList(list));
             list.remove(list.size() - 1);
             helper(res, list, x, i);
             list.remove(list.size() - 1);  
           }
        }
    

Log in to reply
 

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