Share my dfs java code


  • 0

    Each time you search, you iterate a potential factor from a new start to the square root of n. In order to avoid duplicate, the new start should be larger than the factor you previously divide n by.

    public class Solution {
        public List<List<Integer>> getFactors(int n) {
            List<List<Integer>> result = new ArrayList<>();
            
            search(result, new ArrayList<Integer>(), 2, n);
            
            return result;
        }
        
        private void search(List<List<Integer>> result, List<Integer> currList, int floor, int number) {
            for (int i = floor; i <= Math.sqrt(number); i++) {
                if (number % i == 0) {
                    currList.add(i);
                    
                    search(result, currList, i, number / i);
                    
                    currList.add(number / i);
                    result.add(new ArrayList<>(currList));
                    
                    currList.remove(currList.size() - 1);
                    currList.remove(currList.size() - 1);
                }
            }
        }
    }
    

Log in to reply
 

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