CODEWITHSUNDEEP
javaalgorithmrecursiontime-complexitydepth-first-search
KBR
KBR

Reputation: 494

How to find the time complexity of dfs+backtracking algorithms?

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);
            }            
            
        }
        
    }

Upvotes: 4

Views: 3732

Answers (2)

JohnnyHuo
JohnnyHuo

Reputation: 483

Not able to post the solution in the comment. Post as another answer here @AliSoltani https://discuss.leetcode.com/topic/30752/my-short-java-solution-which-is-easy-to-understand

public class Solution {
public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    if(n <= 3)  return ret;
    List<Integer> path = new LinkedList<Integer>();
    getFactors(2, n, path, ret);
    return ret;
}

private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){
   for(int i = start; i <= Math.sqrt(n); i++){
       if(n % i == 0 && n/i >= i){  // The previous factor is no bigger than the next
           path.add(i);
           path.add(n/i);
           ret.add(new LinkedList<Integer>(path));
           path.remove(path.size() - 1);
           getFactors(i, n/i, path, ret);
           path.remove(path.size() - 1);
       }
   }
}}

Upvotes: 0

Ali Soltani
Ali Soltani

Reputation: 9927

I computed complexity of your code like this:

Let's consider the runtime of getFactorsHelper(n,2) is function T(n).

In bellow portion you have a loop with i index.

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);
            }              
        }

The n is divided by i in each iteration. So we have:

(first iteration)

getFactorsHelper(n/2,2,current,result) = T(n/2)

(second iteration)

getFactorsHelper(n/3,3,current,result) <= getFactorsHelper(n/3,2,current,result) = T(n/3)

(third iteration)

getFactorsHelper(n/4,4,current,result) <= getFactorsHelper(n/4,2,current,result) 
= T(n/4)

...

(final iteration)

getFactorsHelper(n/n,n,current,result) <= getFactorsHelper(n/n,2,current,result) = T(n/n) = T(1)

total cost

T(n) <= T(n/2) + T(n/3) + T(n/4) + ... + T(1)

Solving recursive function

order

I hope this can help you.

Upvotes: 6

Related Questions