My Recursive Java Solution(Not Backtracking), 2ms


  • 1
    F

    This is a recursive solution, but it does not follow the regular backtracking pattern. The underlying idea is simple. I'll use 40 as an example:
    The minimum factor to try is 2, and it works: 40=2*20.
    Then, to get the rest of solutions that start with 2, I'll only need to work out all the ways to factorize 20. And for every solution, I only need to add the number 2 to the front. For example, 20 can be factorized as 4 and 5. So, one of all the solutions for 20 is [4, 5]. We only need to add 2 to the front, to get the solution for 40: [2, 4, 5]. This works similarly for [2, 10] and [2, 2, 5].

    By the way, it surprises me that this runs only 2ms, because it involves moving backwards every item in an array by one, and I thought it would run slower than most submissions.

    public class Solution {
        public List<List<Integer>> getFactors(int n) {
            return factorsHelper(n, 2);
        }
        
        private ArrayList<List<Integer>> factorsHelper(int n, int minFactor){
            ArrayList<List<Integer>> solutions = new ArrayList<>();
            ArrayList<List<Integer>> subSolutions;
            int factor, quotient;
            
            for(factor = minFactor, quotient = n/factor; factor <= quotient; factor++, quotient = n/factor) {
                if(n%factor == 0) {
                    ArrayList<Integer> factors = new ArrayList<>();
                    factors.add(factor);
                    factors.add(quotient);
                    solutions.add(factors);
                    subSolutions = factorsHelper(quotient, factor);
                    
                    for(int cnt = 0; cnt < subSolutions.size(); cnt++) {
                        subSolutions.get(cnt).add(0, factor);
                        solutions.add(subSolutions.get(cnt));
                    }
                }
            }
            
            return solutions;
        }
    }

Log in to reply
 

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