树形结构的数据都可以使用深度优先搜索进行遍历。
有些问题的困难在于，将问题转换成树形结构的问题。
例如求集合的子集合。
有一种树形搜索 会在几个 dfs(深度优先搜索的缩写)之后膨胀到很大的规模 ，但是大部分的结果实际上可以通过逻辑判断删除树枝，这种检索方式成为“剪枝+回溯”
剪枝是在适当的时候排除掉不合适的子树，减少了计算过程，回溯则是指在树遍历过程中，遇到剪枝遍历过程回到上一个分叉的过程。
递归本身含有回溯，所以使用递归实现回溯几乎是最合适的方式，当然也可以用栈这样的数据结构来实现。栈具有先进后出的特性，但发生剪枝需要回溯时，用出栈的方式回到上一个分叉点。
问题一：如何将一个集合的幂集合列出
集合
各不相同
的子集有 个
使用回溯的方法
问题二 把一个数字字符串还原成IP地址
数字字符串的点号因为某种原因被抹去了，例如 "255123" 还原成合格的 IP 地址 "25.51.2.3" 是个合法的结果，但很明显不止一种，"2.5.5.123" 也是一种可能
如何不遗漏地罗列所有的可能结果
这是典型的回溯剪枝问题
我们可以把问题转换成一棵树
起初第一段可以是 2,25 255这样从根到第一层，第一层有三个子树，沿着最左边的 2 这个子树，继续将字符串分叉，得到 5, 55, 551 三棵子树，但是 551 是不合法的段，因为它大于 255，因此从这个 551 的节点开始后面的子树都可以芟除。
继续第三和第四层 ...
以下是个草图，描述了如何将字符串 "255123" 逐步拆成一棵回溯树，其中 × 表示剪枝，该树枝生成的结果肯定不合法
回溯树
class RestoreIP {
public:
vector<string> restoreIpAddresses(string s) {
std::string ans;
backTrack(0, 0, s, ans);
return result;
}
void backTrack(int index, int depth, const string & s, string currentStr) {
if (index == s.size() && depth == 4) {
result.push_back(currentStr);
return;
}
if (depth > 4 || index == s.size() || (4 - depth) * 3 < s.size() - index) {
return;
}
for (int i = 0; i < 3; ++i) {
if (i + index >= s.size()) {
return;
}
std::string sec = s.substr(index, i + 1);
int secInt = std::stoi(sec);
if (sec[0] == '0' && sec.size() > 1 ) {
continue;
} else if (secInt >= 0 && secInt <= 255) {
if (depth > 0) {
backTrack(index + sec.size(), depth + 1, s, currentStr + "." + sec);
} else {
backTrack(index + sec.size(), depth + 1, s, currentStr + sec);
}
}
}
}
vector<string> result;
};
用一个可变数组来存储合格的结果
剪枝逻辑：if (depth > 4 || index == s.size() || (4 - depth) * 3 < s.size() - index) 表示的意思是 深度超过 4 但是还有字符，或者余下的字符无论如何都会有剩余，则剪枝。比如已经选定了前两节是 10.20 余下七个字符，说明无论怎样都不可复原，此时提前剪枝，省去很多计算。
currentStr 是一个追踪当前未完成的 IP 串的变量，一旦检测到它满足 IP 地址的特征，那么就会添加到 可行结果中，否则回溯到上一层，由于 currentStr 是一个传值的变量，回溯到上一层会让 currentStr 移除掉不满足条件的那一节。
例如10.20 如果下一节是300，那么 currentStr = 10.20.300， 检测300大于255 不符合要求，回溯到上一层时，currentStr = 10.20，假设三种可能得子树都不满足条件，那么继续回溯到 currentStr = 10
网友评论