I am trying to solve this problem on leetcode https://leetcode.com/problems/factor-combinations/description/
Numbers can be regarded as product of its factors. For example
8 = 2 x 2 x 2; = 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
while I am able to write the code using dfs approach , I am having hard time in driving its worst case time complexity in terms of input. Can anyone please help?
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> current = new ArrayList<Integer>();
getFactorsHelper(n,2,current,result);
return result;
}
public void getFactorsHelper(int n,int start,List<Integer> current, List<List<Integer>> result){
if(n<=1 && current.size()>1){
result.add(new ArrayList<>(current));
return;
}
for(int i=start;i<=n;i++){
if(n%i==0) {
current.add(i);
getFactorsHelper(n/i,i,current,result);
current.remove(current.size()-1);
}
}
}