1ms DFS JAVA


  • 2
    Q

    Only search the number that is smaller or equals to sqrt(n) to avoid repeated combinations, pass a start value to the next level to optimize the iteration and eliminate repeated combinations by search the factors in ascending order.

    public class Solution {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        public List<List<Integer>> getFactors(int n) {
            getFactors(n, new ArrayList<Integer>(), 2);
            return result;
        }
        public void getFactors(int n, List<Integer> iList, int st){
            for(int i = st; i * i <= n; ++i){
                if(n % i == 0){
                    iList.add(i);
                    iList.add(n/i);
                    result.add(new ArrayList<Integer>(iList));
                    iList.remove(iList.size()-1);
                    getFactors(n/i, iList, i);
                    iList.remove(iList.size()-1);
                }
            }
        }
    }

Log in to reply
 

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