有人能告诉我为什么这段代码使用 DFS 吗？

Question

我知道如果我们处理图 DFS，我们使用堆栈来跟踪访问的节点。但是下面的代码也使用了 DFS。看了好几遍还是不知道在哪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);  
     }  
 }

Answer 1

DFS 可以使用 2 种基本技术实现：

1。使用堆栈

2。使用递归。

我知道您很难相信您提供的代码正在使用 DFS，因为您在任何地方都看不到显式堆栈。原因是因为它使用第二种技术实现了 DFS。

第二种技术也很容易实现。它的伪代码非常简单。

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

您提供的代码仅使用了这种简单的技术，但是如果您学习过操作系统课程，您就会知道递归使用程序堆栈来跟踪函数调用，因此您仍在间接使用堆栈，但这是一个不同的问题。

有人能告诉我为什么这段代码使用 DFS 吗？

Can someone tell me why this code uses DFS?

depth-first-search