Search

[caipengbo]

目录

• Combination 组合
• Permutation 排列

[caipengbo]

递归，回溯和DFS的区别

递归是一种算法结构，回溯是一种算法思想
一个递归就是在函数中调用函数本身来解决问题
回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。

回溯搜索是深度优先搜索（DFS）的一种对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。回溯使用了DFS
回溯 = DFS + Pruning

其实本质上所有的搜索问题都可以看成一个树结构，DFS应用于典型的树结构，回溯应用于广义的树结构（棋盘问题，数独）

[caipengbo]

回溯算法的标准模板

参数：原始参数（题目必备的参数）、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;
}

[caipengbo]

Combination 组合

相关题目：17、22、39、40、77、216

典型的回溯算法，使用一个循环，一个一个去组合（注意从start开始，避免重复），然后递归进行，递归完，移除之前的操作（回溯）

关于重复元素问题（下面的排列、子集等问题也会遇到重复元素问题）的解决办法：先排序、然后在剪枝语句中添加 if( element[i] == element[i-1] ) continue;

[caipengbo]

Permutation排列问题

相关题目：46、47、784、996

和Combination类似，只不过每一次的循环从 0开始

[caipengbo]

SubSet问题

**相关题目：**78、90、842
和组合问题一致，只不过退出条件可能要添加一个size == 子集的数目，这么一个判断条件

[caipengbo]

Partition 分割问题

[caipengbo]

N皇后与数独问题

[caipengbo]

迷宫问题（棋盘问题）

[caipengbo]

其他回溯：产生括号问题

[caipengbo]

回溯的基本写法

[caipengbo]

BFS