DFS通用解法
DFS通用解法
最近在刷一些算法题，发现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来标示，具体查看