Simple Java Recursive Solution


  • 3
    N
    public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> list = new ArrayList<>();
    
        list = perform(n, list, new ArrayList<Integer>());
        return list;
    }
    
    private List<List<Integer>> perform(int n, List<List<Integer>> list, List<Integer> l){
        for(int i=2;i<n;i++){
            if(n%i==0 && i<=n/i && (l.size()==0 || l.get(l.size()-1) <= i)){
                List<Integer> temp  = new ArrayList<Integer>(l);
                temp.add(i);
                list = perform(n/i, list, temp);
                temp.add(n/i);
                list.add(temp);
            }
        }
        return list;
    }
    

    }


  • 0
    Y

    you can change i<n in the for condition to i*i<=n ,then the runtime goes down from 244ms to 2ms :)


  • 0
    E

    @Yun.Hu nice catch!


  • 0
    Z

    Just one suggestion.

    When writing recursion, it's better to get context knowledge from caller, rather than calculating it inside recursion. The context knowledge here is the starting number which is calculated by this code :

    (l.size()==0 || l.get(l.size()-1) <= i)

Log in to reply
 

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