深度优先搜索解题思路
深度优先搜索特点
深度优先搜索通常用来解决如下问题：
- 在搜索空间中寻找一条路径
- 寻找所有符合要求的路径
- 找出最佳路径
搜索空间有时候是具体的，有时候是抽象的。比如搜索空间是一棵树或者一幅图，这就是具体的搜索空间。还有的情况，比如把一个数 n 分成 n = a^2 + b^2 + c^2 + ... 的形式，这里的搜索空间就是抽象的，是在一个数字集合中反复搜索。
深度优先搜索，即从某一点出发，不断深入，中途会记录下途经的所有节点（即路径）。想象你在一个迷宫中寻找宝石。手里拿这一个绳子，无论你进入多么深的岔路，绳子总是记录着行走的路径。当走进一个死胡同，你原路返回到前一个路口，然后进入其他岔路。你不断尝试新的岔路，中途会寻找到宝石，此时可以记录下绳子（路径）的状态，然后继续寻找下一个宝石。当你寻找完迷宫里的各条岔路后，也就完成了对迷宫的深度优先收缩。
深度优先搜索解题模版
深度优先搜索的模板如下，大部分深度优先搜索问题都可以落入此模板中：
def dfs(input, path, result, current):
if <搜索到了结果>:
result.append(path)
return
if <搜索区域超出范围 or 数据非法>:
return
if <可以减枝>:
return
for n in <下一步搜索点>:
path.append(n) # 把下一个点加入中间结果中
dfs(input, path, result, <更新后的 current>)
path.pop() # 恢复中间结果
# 调用函数，通常需要做的就是把参数定义好，并调用 dfs
def main(nums, target):
result = []
path = []
dfs(nums, path, result, target)
return result
dfs 中的 path 记录了遍历的路径，因为是深度优先搜索，你进入了一个个分岔路口，但是 path 记录了走过的一个个路口，当你回退回来的时候，path 中会删除掉此路口。因此 path 在深度优先搜索中是从头至尾可以复用的。
某些搜索空间，节点中存在环路，比如图，之前访问过的点，可能在之后又绕回来了，最终无限地兜圈子。对于这种场景，需要使用额外的辅助空间来记录下已经访问过的点，下次遇到此点时要立即退出。
深度优先搜索是一种搜索策略，它和回溯法联系紧密，回溯法就是深度优先搜索，只是回溯法会在搜索过程中加入一些剪枝条件加快搜索过程。而深度优先搜索这个词指的可能只是搜索，但是通常也都要加入各种剪枝策略，避免没有必要的搜索。深度优先搜索和回溯法几乎可以划等号。
实例
题目描述见这里：无重复字符串的排列组合
本题需要找出给定字符串的所有排列组合，生成一个排列组合的方法是，先取一个字符，然后在余下的字符中再选一个，以此类推知道消耗完所有字符。每次选取时取的字符不同，最终就构成了排列组合。
因此，可以使用深度优先搜索，每次取一个字符，在 dfs 的过程中保存下遍历的路径，当该路径长度等于原字符串时，就停止遍历。但是为了避免重复取某个字符，需要把取过的字符记录下来。
class Solution {
public:
vector<string> permutation(string s) {
vector<string> result;
vector<bool> visited(s.size(), false);
string path;
dfs(path, s, visited, result);
return result;
}
void dfs(string& path, const string &s, vector<bool>& visited, vector<string>& result){
if(path.size() == s.size()){
result.push_back(path);
return;
}
for(int i = 0; i < s.size(); i++){
if(visited[i]){
continue;
}
visited[i] = true;
path += s[i];
dfs(path, s, visited, result);
visited[i] = false;
path.pop_back();
}
}
};
如果搜索空间是一个图，那么标记已经访问的点是非常有必要的，通常使用下标来进行标记。有同学可能会使用 set 来存储字符来进行标记，在这里是没有问题的，但如果存在重复的字符就不行了。因此，考虑使用唯一的东西进行标记。而如果搜索空间是树，那自然就不需要标记了。
下面可以在看看此题的衍生版本 有重复字符串的排列组合，如果字符串中存在重复，在 dfs 中的 for 循环需要保证只选择相同的字符一次。
其他实例
下面这些题目都采用深度优先搜索，可以结合上面介绍的套路，实际动手完成这些例题，加深对深度优先搜索的理解。