回溯法

组合总和 II题目介绍给定一个候选人编号的汇合 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能应用 一次 。 留神：解集不能蕴含反复的组合。 示例： 输出: candidates = [10,1,2,7,6,1,5], target = 8,输入:[[1,1,6],[1,2,5],[1,7],[2,6]]示例： 输出: candidates = [2,5,2,1,2], target = 5,输入:[[1,2,2],[5]]问题剖析办法一在这道问题当中咱们依然是从一组数据当中取出数据进行组合，而后失去指定的和，然而与后面的组合总和不同的是，在这个问题当中咱们可能遇到反复的数字而且每个数字只可能应用一次。这就给咱们减少了很大的艰难，因为如果存在雷同的数据的话咱们就又可能产生数据雷同的组合，比方在第二个例子当中咱们产生的后果[1, 2, 2]其中的2就可能来自candidates当中不同地位的2，能够是第一个，能够是第三个，也能够是最初一个2。然而在咱们的最终答案当中是不容许存在反复的组合的。当然咱们能够依照失常的形式遍历，而后将失去的复合要求的后果退出到一个哈希表当中，对失去的后果进行去重解决。然而这样咱们的工夫和空间开销都会加大很多。 在这个问题当中为了防止产生反复的汇合，咱们能够首先将这些数据进行排序，而后进行遍历，咱们拿一个数据来进行举例子：[1, 2 1]，当初咱们将这个数据进行排序失去的后果为：[1, 1, 2]，那么遍历的树结构如下： 上图示意[1, 1, 2]的遍历树，每一个数据都有选和不选两种状况，依据这种剖析形式能够结构下面的解树，咱们对下面的树进行剖析咱们能够晓得，在下面的树当中有一部分子树是有反复的（反复的子树那么咱们就回产生反复的后果，因而咱们要删除反复的分支，也就是不进行递归求解），如下图所示： 咱们当初来剖析一下下面图中产生重复子树的起因，在一层当中选1的到第二层不选1的子树和第一层不选1而第二层选1的树产生了反复，因而咱们能够在第一层不选1第二层选1的子树当中进行递归。 依据下面的例子咱们能够总结进去，在同一层当中，如果前面的值等于他后面一个值的话，咱们就能够不去生成“抉择”这个分支的子树，因为在他的后面曾经生成了一颗截然不同的子树了。 当初咱们的问题是如何确定和上一个遍历的节点是在同一层下面。咱们能够应用一个used数组进行确定，当咱们应用一个数据之后咱们将对应下标的used数组的值设置为true，当递归实现进行回溯的时候在将对应地位的used值设置为false，因而当咱们遍历一个数据的时候如果他后面的一个数据的used值是false的话，那么这个节点就和后面的一个节点在同一层下面。 依据下面的剖析咱们能够写出如下的代码： class Solution { vector<vector<int>> ans; vector<int> path;public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<bool> used(candidates.size(), false); backtrace(candidates, target, 0, 0, used); return ans; } void backtrace(vector<int>& candidates, int target, int curIdx, int curSum, vector<bool>& used) { if (curSum == target) { // 满足条件则保留后果而后返回 ans.push_back(path); return; } else if (curSum > target || curIdx >= candidates.size()) { return; } if (curIdx == 0) { // 抉择分支 path.push_back(candidates[curIdx]); used[curIdx] = true; backtrace(candidates, target, curIdx + 1, curSum + candidates[curIdx], used); // 在这里进行回溯 path.pop_back(); used[curIdx] = false; // 不抉择分支 backtrace(candidates, target, curIdx + 1, curSum, used); }else { if (used[curIdx - 1] == false && candidates[curIdx - 1] == candidates[curIdx]) { // 在这里进行判断是否在同一层，如果在同一层并且值相等的话 那就不须要进行抉择了 只须要走不抉择的分支及即可 backtrace(candidates, target, curIdx + 1, curSum, used); }else{ // 抉择分支 path.push_back(candidates[curIdx]); used[curIdx] = true; backtrace(candidates, target, curIdx + 1, curSum + candidates[curIdx], used); // 在这里进行回溯 path.pop_back(); used[curIdx] = false; // 不抉择分支 backtrace(candidates, target, curIdx + 1, curSum, used); } } }};办法二在回溯算法当中咱们个别有两种抉择状况，这一点咱们在后面组合问题当中曾经介绍过了，一种办法是用抉择和不抉择去生成解树，这样咱们将生成一颗二叉树的解树，另外一种是多叉树，上面咱们来看一下后者的解树： ...

通过组合问题看透回溯法前言曾经良久没有更新了，从明天开始要保障每周的更新频率了（立个flag，应该可能想到打脸会来的很快），明天给大家分享一道LeetCode算法题，题目不是很艰难，然而从这到简略的题目咱们能够剖析出回溯算法的几个外围要点，当前遇到须要回溯的题目能够应答的思路，晓得应该怎么思考，朝什么方向去寻找解决问题的进口！ 题目给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。你能够按 任何程序 返回答案。例子： 输出：n = 4, k = 2输入：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]解法解法一乍一看这道题如同是一个很间接的问题，咱们只须要从[1, n]当中选出k个数据进去，比如说题目当中给出的，咱们须要从[1, 4]这个区间取出两个数，那么咱们只须要应用两层for循环即可，像上面这样： for (int i = 1; i <= n; i++) { // 在这里抉择 i for (int j = i + 1; j <= n; j++) { // 每一次循环抉择 j }}然而遗憾的是k是一个变量，它不是一个定值，如果他是一个定值的话，那么咱们就能够应用下面的循环操作去解决这个问题，而且是很高效的。那这个问题咱们应该如何解决的？咱们思考一下，对于每一个数咱们都有两种抉择：抉择和不抉择，也就是是否须要将这个数据加到汇合当中去。 当初咱们对上述给定的例子进行求解（n = 4, k = 2），每一个数据都有两种抉择，选和不选（很多回溯的问题都是能够依照这种思路）具体过程入下图所示，其中蓝色的节点示意待抉择的数据，红色的框示意以后被选中的数据的汇合： 上图是上文当中给出的例子的解树，其中绿色的节点示意最终的答案，对于每个节点的数据都有两种抉择方法，选和不选，因而下面的解决问题的树结构是一个齐全二叉树，咱们能够应用深度优先遍历去实现下面的解题过程。从上图来看咱们能够进行一些剪枝，当咱们选中的数据的个数曾经达到k的时候咱们不须要在进行递归，因为咱们须要的数据长度是固定的，当达到指定数目的数据个数之后咱们不须要再退出数据了，因而也没有持续往下遍历的必要了。具体看下图，其中紫色节点示意不须要进行递归的节点，因为在遍历他们之前咱们都曾经失去一个后果了： 因而当咱们选中的元素达到k个的时候，咱们就能够退出递归，因而这是咱们的一个递归进口，咱们在设计回溯函数的时候须要实现这个进口。 除了下面提到的递归进口之外咱们还有另外一个暗藏的递归进口。当咱们以后抉择的数据的个数加上前面还剩下的所有的数据的时候还达不到咱们所须要的数据的个数k的时候，咱们也不须要在进行遍历了，能够间接退出递归了，比方下面用红色标记的节点，因为即便加上了前面残余的所有的数据也不可能满足条件。 依据下面咱们的思路和两个递归进口，咱们能够写出上面的代码： public void backTrace(int n, int k, List<Integer> path, int idx) { // idx 示意以后正在遍历的数据 if (path.size() == k){ // 如果选中的数据个数达到 k 了那么咱们须要将以后选中数据的汇合退出到咱们返回的数据当中 ans 示意咱们最终须要返回的后果 外面的内容是 有 k 个数据的汇合 ans.add(new ArrayList<>(path)); return; } else if ((path.size() + n - idx + 1) < k) return; path.add(idx); // 退出一个数据 示意抉择数据 idx backTrace(n, k, path, idx + 1); path.remove(path.size() - 1); // 移出下面退出的数据 示意在这里进行回溯 因为咱们是深度优先遍历，后面将 idx 退出到了 path 当中 当递归返回的时候咱们须要将退出的数据移出 因为这里示意不抉择数据 idx backTrace(n, k, path, idx + 1);}残缺代码如下： ...

开始二刷回溯算法，这里对回溯法开展思考，加深对其的原理和利用场景的了解。以组合问题为例：给定两个整数 n 和 k，返回范畴[1, n]中所有可能的 k 个数的组合。 和遍历，递归这种算法比照起来如同更简单了一点儿。如二分法这种，个别都是间接遍历，通过一直地循环遍历判断找到答案。递归：二叉树的遍历，一直调用递归函数，能够是从头到尾，从尾到头。回溯，在递归的根底上有一个重要的区别在于，有待选区间。 如此一比照，其实发现，在二叉树的递归遍历上，也存在一个指定区间的过程，只不过是一直的把左节点或者右节点，这样单个节点传进去。回溯的做法区别在于，对于一个候选数据结构为数组或者数来说，利用startIndex 来束缚抉择的范畴。实现在每一次的操作中，依据startIndex来更新可抉择的区间。 联合代码来看： class Solution {public: vector<vector<int>> result; vector<int> path; void backtracking(int n, int k, int startIndex) { if (path.size() == k) { result.push_back(path); return ; } for (int i = startIndex; i <= n; i++) { path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracking(n, k, 1); return result; }};实际上和树的遍历很像。结构回溯函数（实质上其实就是递归函数），先判断完结条件，在以后层进行遍历待选择项。先进行操作，而后持续回溯（有点儿深度优先的象征在外面）。能够思考什么时候进入path.pop_back()语句，发现这个过程蛮有意思的，去思考过后，比拟了解了为何代码随想录中将其比喻成数的构造，因为在回溯函数中有一个for语句的存在，因而在进入每一层的时候，都有一个待选数据的存在。