CODEWITHSUNDEEP
depth-first-search
msProgram
msProgram

Reputation: 117

Can someone tell me why this code uses DFS?

I know if we deal with graph DFS, we use stack to track the node visited. But the code below is also using DFS. I read it a few times but still cannot figure out where it is DFS.Thanks!

 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {  
     ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();  
     ArrayList<Integer> item = new ArrayList<Integer>();
     if(candidates == null || candidates.length==0)  
         return res; 

     Arrays.sort(candidates);  
     helper(candidates,target, 0, item ,res);  
     return res;  
 }  

 private void helper(int[] candidates, int target, int start, ArrayList<Integer> item,   
 ArrayList<ArrayList<Integer>> res){  
     if(target<0)  
         return;  
     if(target==0){  
         res.add(new ArrayList<Integer>(item));  
         return;  
     }

     for(int i=start;i<candidates.length;i++){  
         if(i>0 && candidates[i] == candidates[i-1])
         item.add(candidates[i]);
         int newtarget = target - candidates[i];
         helper(candidates,newtarget,i,item,res);
         item.remove(item.size()-1);  
     }  
 }

Upvotes: 0

Views: 59

Answers (1)

Sumeet
Sumeet

Reputation: 8292

The DFS can be implemented using 2 basic techniques:

1. Using Stack

2. Using Recursion.

I know that you find it hard to believe that the code you provided is using DFS because you don't see an explicit stack anywhere. The Reason is because it has implemented DFS using the second technique.

And the second technique is very easy to implement too. The psuedocode for it is very simple.

DFS( vertex v )
{
 mark v visited
 for all unvisited vertices u adjacent to v
 {
    DFS(u)
 }
}

The code you provided is using this simple technique only, but if you have studied the course Operating System, you will come to know that recursion uses the program stack to keep track of function calls, so you are indirectly still using stack, but that is a different issue.

Upvotes: 2

Related Questions