Accepted Java DFS solution


  • 0
    L
        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>> res = new ArrayList<>();
            helper(n, 2, new ArrayList<>(), res);
            return res;
        }
        
        public void helper(int n, int start, List<Integer> list, List<List<Integer>> res) {
            //Using 'start' to avoid the case like [3,2,2] for the factor combinations of 12
            for (int i = start; i * i <= n; i++) {
                if (n % i == 0) {
                    //The current n could be divided by i, so it is one of factor combinations and add it to the result
                    //For example, to factor 32, 2 is already in the list, n is 16 now, so add [2, 2, 8] to the result, then we factor 8
                    List<Integer> tmp = new ArrayList<>(list);
                    tmp.add(i);
                    tmp.add(n / i);
                    res.add(tmp);
                    
                    list.add(i);
                    helper(n / i, i, list, res);
                    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.