caipengbo
Search
递归，回溯和DFS的区别
递归是一种算法结构，回溯是一种算法思想 一个递归就是在函数中调用函数本身来解决问题 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。
回溯搜索是深度优先搜索（DFS）的一种对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。回溯使用了DFS
回溯 = DFS + Pruning
其实本质上所有的搜索问题都可以看成一个树结构，DFS应用于典型的树结构，回溯应用于广义的树结构（棋盘问题，数独）
回溯算法的标准模板
参数：原始参数（题目必备的参数）、start（开始位置）， cur（当前答案）, ans（保存的所有答案）
Java中注意如果将当前答案添加到最终ans list时，要new一个新的对象
// 找到所有方案
void findSolutions(n, other params) {
if (found a solution) { // 找到一个答案
// solutionsFound = solutionsFound + 1;
addSolution(); // 将当前solution添加到solution list中
// if (solutionsFound >= solutionTarget) :
// System.exit(0);
return
}
// 有的写不成循环，要分多个情况进行讨论；本质上循环就是多个情况，只不过写起来比较简单而已
for (val = first to last) { // or start（开始位置参数） to last
if (! isValid(val, n)) continue; // 剪枝
applyValue(val, n); // 改变参数
findSolutions(n+1, other params);
removeValue(val, n); // 取消 改变参数
}
}
// 一个方案是否存在
boolean findSolutions(n, other params) {
if (found a solution) {
displaySolution();
return true;
}
for (val = first to last) { // or start（开始位置参数） to last
if ( !isValid(val, n)) continue;
applyValue(val, n);
if (findSolutions(n+1, other params)) return true;
removeValue(val, n);
}
return false;
}
Combination 组合
相关题目：17、22、39、40、77、216
典型的回溯算法，使用一个循环，一个一个去组合（注意从start开始，避免重复），然后递归进行，递归完，移除之前的操作（回溯）
关于重复元素问题（下面的排列、子集等问题也会遇到重复元素问题）的解决办法：先排序、然后在剪枝语句中添加 if( element[i] == element[i-1] ) continue;