Java recursion, easy. fast.


  • 0
    Z

    Note:let caller pass context knowledge! dont let callee calculate it. Parameter start is an example of context knowledge.

      public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ret = new ArrayList<>();
        if(n == 1)
            return ret;
    
        List<Integer> sofar = new ArrayList<>();
        helper(ret,sofar, n, 2 /*start*/);
        return ret;
    }
    
    void helper(List<List<Integer>> acc, List<Integer> sofar, int n, int start){
        if(n == 1){
            if(sofar.size() > 1)
                acc.add(new ArrayList<>(sofar));
            return;
        }
    
        // finding factors.
        for(int i = start; i*i <= n; ++i ){
            if(n % i ==0){
                sofar.add(i);
                helper(acc, sofar, n / i , i);
                sofar.remove(sofar.size()-1);
            }
        }
    
        // try n alone.
        sofar.add(n);
        helper(acc, sofar, 1 , n);
        sofar.remove(sofar.size()-1);
    
    }

Log in to reply
 

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