系列文章目录

---

---

前言

本文所述的深度优先搜索算法主要针对树状结构，其中的树的每个节点都可以包含0到多个子节点。
深度优先，即为先纵向搜索树的枝干，搜索到该枝干的叶子节点后返回，再搜索另一条枝干(横向搜索)，从而在纵向和横向上实现对整个树形结构的全遍历。

---

一、代码模板

深度优先搜索算法，有人也将其成为回溯法，即优先搜索值树的叶子节点，然后递归调用返回(即为回溯)，接着搜索同层的下一个节点。

结论：递归调用进入树的下一层节点，for循环遍历同层内的下一个节点

void depthFirstSearch(arg...) {if (结束递归判定) {// 一些处理return;}// may be need somethingfor (i=开始搜索 ; i < 结束条件; 处理i) { // 搜索本层的节点// 前处理，处理该节点，比如push_backdepthFirstSearch(arg...); // 递归调用，搜索下一层// 下一层搜索完毕后函数返回，进行后处理,比如pop_back}
}

二、题目案例

77.组合

class Solution {vector<vector<int>> res;void backtracking(int n, int k, int idx, vector<int>& proper){if (proper.size() == k) {res.push_back(proper);    return;}for (int i = idx; i <= n - (k-proper.size()) + 1; ++i){proper.push_back(i);backtracking(n, k, i+1, proper);proper.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {vector<int> proper;backtracking(n, k, 1, proper);return res;}
};

40. 组合总和 II

class Solution {vector<vector<int>> res;void backtracking(vector<int>& candidates, int target, int sum, int idx, vector<int>& node){if (sum == target){res.push_back(node);return;}int prev = 51;for (int i=idx; i < candidates.size() && sum < target; ++i){// if (i>0 && (candidates[i-1] == candidates[i]) ) continue;if (prev == candidates[i]){continue;}prev = candidates[i];node.push_back(candidates[i]);backtracking(candidates, target, sum + candidates[i], i+1, node);node.pop_back();}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<int> node;backtracking(candidates, target, 0, 0, node);return res;}
};

---

总结