最近在刷一些算法题，发现DFS在单链表，二叉树，图，集合的解题比较多，具有一定的通用规律，现在讲通用方法记录下。拿二叉树举例，比如我们需要从根走到叶子节点才能得到一个解，这种类型非常适合是用DFS，再以二维数组举例，我们可以将二维数组当成一个图，进行搜索，在搜索的同事满足一定的匹配等。

一般情况下Wide-FS只要求有一个解，而且需要将整个中间状态存储到内存中，而DFS只存储一条路径，非常时候解决一些问题。

在DFS中我们需要一个收敛条件，也就是合法解。这时我们就需要把这个中间状态保存到最后的结果中。为了加快深搜，我们可以剪枝，常用方式使用状态数组表示，提前return，可以大大加快递归速度。

通用dfs模板：

/**
* dfs 模板.
* @param[in] input 输入数据指针
* @param[out] path 当前路径，也是中间结果,可以是一维数组
* @param[out] result 存放最终结果，二维数组
* @param[inout] cur or gap 标记当前位置或距离目标的距离，或者可以
* 是start end等标记
* @return 路径长度，如果是求路径本身，则不需要返回长度
* 可以返回bool等，依照题目要求来实现。
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作，修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

这里我举一个例子：列举所有set可能的子集合，比如S=[1,2,3],那么结果是[[3],[2],[1],[1,2,3],[1,3],[2,3],[1,2],[]]
解决这个问题，需要首先按照上面的这种模板构建，首先是这个dfs的input 也就是这个S，中间路径path与S类型相同。结果应该是一个二维数组，也就是vector< vector > result,最后我们需要一个step作为收敛条件。

void dfs(const vector<int> &S, vector<int> &path, vector<vector<int> > &result,int step) {
     if (step == S.size()) {//到达S.size()收敛
           result.push_back(path);
           return;
     }
     //这里没有剪枝
     // 不选S[step]
     subsets(S, path, step + 1, result);
     // 选S[step]
     path.push_back(S[step]);
     subsets(S, path, step + 1, result);
     path.pop_back();
}
 void dfs(vector<int>& nums,vector<int> &path,vector<vector<int>> &result,
                     vector<int>::iterator start){
 
     result.push_back(path);
 
     for(auto i = start;i<nums.end();i++)
     {
          path.push_back(*i);
          dfs(nums,path,result,i+1);
          path.pop_back(); 
     }
 }

深度搜索比较难以理解，层层递归会让我迷失，不过进行断点认真跟踪是可行的。最后跟踪断点结果是：

[]
3
2
2,3
1,
1,3
1,2
1,2,3

还有很多场景，比如二维数组寻路，都会用到上下左右的移动，还要使用flag来标示，具体查看
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/word-search/