本文共 4908 字，大约阅读时间需要 16 分钟。
回溯法
回溯法概念 回溯算法有“通用的解题法”之称。用它可以系统地搜索一个问题的所在解或任一解。回溯法是一个即带有系统性又带有跳跃性的所搜算法。回溯法思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
回溯法解题步骤
用回溯法解题通常包含以下3个步骤： 1. 针对所给问题，定义问题的解空间 2. 确定易于搜索的解空间结构 3. 以深度优先方式所搜解空间，并在搜索过程中用剪枝函数避免无效搜索。回溯算法一般框架
int solution[MAX_DIMENSION]; //多维度解void backtrack(int dimension){ /*检验当前维度数组是否是一个解*/ if ( solution[] is well-generated ) { check and record solution; return; } /* 列举当前维度的所有取值的情况，并且进入到下一维度*/ for ( x = each value of current dimension ) { solution[dimension] = x; backtrack( dimension + 1 ); }} backtrack( [v1,...,vn] ) // [v1,...,vn]是多维度数值{ /*检验当前多维度数值是不是一个解*/ if ( [v1,...,vn] is well-generated ) { if ( [v1,...,vn] is a solution ) process solution; return; } /* 列举当前维度的所有取值的情况，并且进入到下一维度*/ for ( x = possible values of vn+1 ) backtrack( [v1,...,vn, x] );} 使用回溯法解决排列问题 Question: 列出 {0,1,2,3,4} 所有的排列 int solution[5];bool use[5] = {false};void backtrack(int n) { if (n == 5) { //processing solution for(int i = 0; i < n; ++i) cout << solution[i] << " "; cout << endl; return; } else { //列举{0,1,2,3,4}所有可能的值 for (int i = 0; i < 5; ++i) { if (!use[i]) { use[i] = true; solution[n] = i; backtrack(n+1); //进入到下一个维度 use[i] = false; } } }}int main(){ backtrack(0); return 0;} Question: 列举abb所有不相同的排列 首相我们先来写abc所有的排列算法。而abc的排列算法与上面的问题是一样的，稍微进行修改就可。这里我们将不再使用全局数组solution来保存结果。 void backtrack(const vector如果直接使用上面的程序进行abb排列，则输出结果为&num, vector use, vector solution){ if (solution.size() == 3) { //注意本列中abb排列的结果维度为3 for(const auto e : solution) cout << e << " "; cout << endl; return; }else { for(int i = 0; i < num.size(); ++i) { if (!use[i]) { use[i] = true; solution.push_back(num[i]); backtrack(num, use, solution); solution.pop_back(); use[i] = false; } } }}
a b ca c bb a cb c ac a bc b a会出现这个情况，是因为上面的程序中认为输入的字符数组中没有相同的字符，即使有相同的字符也会当成不同对待。因此才会出现相同的排列的情况。为了避免重复的排列，我们首先对输入的字符进行排序，使得相同的字符连续出现。然后使用一个标记位来标记上一次出现的字符。
void backtrack(const vector使用回溯法解决子集合问题 Question : 给定一个没有重复元素的数组nums，求它所有的子集合. 例如 nums = [1,2,3]的子集合为：&num, vector use, vector solution){ if (solution.size() == 3) { for(const auto e : solution) cout << e << " "; cout << endl; return; }else { char prevChar = '\0'; for(int i = 0; i < num.size(); ++i) { if (!use[i] && prevChar != num[i]) { prevChar = num[i]; use[i] = true; solution.push_back(num[i]); backtrack(num, use, solution); solution.pop_back(); use[i] = false; } } }}
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
class Solution {public: vector > subsets(vector & nums) { vector > solution; vector subset; backtrack(nums, 0, subset, solution); return solution; }private: void backtrack(vector &nums, int start, vector &subset, vector > &solution) { solution.push_back(subset); for (int i = start; i < nums.size(); ++i) { subset.push_back(nums[i]); backtrack(nums, i+1, subset, solution); subset.pop_back(); } }}; Question : 接着上一个问题，如果输入数组中可能有重复的元素，求所有不相同的子集合 与上面求abb所有的排列类似，在有相同元素时，首先对元素进行排序，然后使用标志位来记录上一次的取值。 class Solution {public: vector > subsetsWithDup(vector & nums) { sort(nums.begin(), nums.end()); //首先对数组进行排序 vector > solution; vector subset; backtrack(nums, 0, subset, solution); return solution; }private: void backtrack(vector &nums, int start, vector &subset, vector > &solution) { solution.push_back(subset); int prevNum = INT_MAX; for (int i = start; i < nums.size(); ++i) { if (nums[i] != prevNum) { prevNum = nums[i]; subset.push_back(nums[i]); backtrack(nums, i+1, subset, solution); subset.pop_back(); } } }}; reference 计算机算法设计与分析(第三版) 王晓东 编著 回溯法笔记 ———————————————— 版权声明：本文为CSDN博主「Kavin_Liang」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/shinanhualiu/article/details/52016481