Share my 11-line java code with brief explanation


  • 1
    M
    public class Solution {
        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>> ans = new ArrayList<>();
            dfs(ans, new ArrayList<Integer>(), 2, n);
            return ans;
        }
        
        private void dfs(List<List<Integer>> ans, List<Integer> list, int prevFactor, int currentN) {
            for (int i=prevFactor; i*i<=currentN; ++i) {
                if (currentN%i == 0) {  // i is a factor of current n
                    list.add(i);
                    list.add(currentN/i);
                    ans.add(new ArrayList<Integer>(list));  // first, add (i, n/i) to answers
                    list.remove(list.size()-1);
                    dfs(ans, list, i, currentN/i);  // continue to the next level of search
                    list.remove(list.size()-1);
                }
            }
        }
    }
    
    1. for each level, we only need traverse through [factor of previous level, sqrt("current n")]
    1. at first level, we start from trying factor 2.

Log in to reply
 

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