回溯问题的去重技巧

1. 回溯问题

在leetcode中我们经常会遇到很多需要求解一组集合或者所有排列的问题，这类问题的难点在于，通常情况下我们只有暴力求解这一种方式，通过遍历所有可能的解，从中找到符合我们要求的题解。常见的回溯问题包括以下类别：组合（不要求顺序，元素相同顺序不同的视为同样的答案），排列（要求顺序，相同元素不同顺序视为不同答案），切割，子集，棋盘（N皇后，数独）等。这类问题有一个共同特点就是可以抽象为树性结构，其中，所遍历的集合的大小构成了树的宽度，递归的深度构成了树的深度。下面我们给出回溯函数的模板，包括返回值、参数以及写法：

• 回溯方法的函数伪代码

    void backtarcking(参数)
  

这里我们使用void作为回溯函数的返回值，因为我们需要做的是在集合中寻找符合题意的解，那么就可以设置一个result数组来保存符合题意的解，在递归调用的过程中，不断将解加入result即可，函数遇到终止条件就可以return。

• 回溯函数的终止条件

  终止条件视情况而定，有可能是遍历到叶子节点，有可能是需要满足一些条件，在backtracking函数中，首先要做的就是判断是否触发了终止条件，如果触发了，那么就处理当前的结果，需要的话还要return，这里的关键是，如果需要遍历所有情况，则不需要return，因为其会导致后面的通往叶子节点的路径不会被遍历到。如果需要剪枝的话，则需要return。终止条件的伪代码为：

    if(终止条件){
        处理结果；
        (return, 视情况而定)
    }
  

  还需要注意的是，有些寻找子集的问题或者排列组合的问题中，并不需要终止条件，此时只需要处理结果就可以。

• 回溯函数的递归部分

  递归部分是回溯函数的核心，只有把递归部分写的明白，才算真正懂得了何为“回溯”，所谓回溯就是指在遍历过程中保存的中间结果，在之后的遍历时仍然需要，那么就需要保存起来，常用的方法是使用path数组保存起来，遍历到当前节点时，将节点信息保存至path中，遍历后，在将最后一个保存的信息弹出，这样path中最后保存的就是前一个节点的信息。递归部分的伪代码：

    for(int i = startIndex; i < size; i++){
        处理节点
        path.push_back(当前节点)
        backtracking(i + 1, 其他参数)；
        path.pop_back(); // 回溯
    }
  

2. 回溯问题中的去重技巧

在回溯问题中有这样几道题，比如Leetcode - 40。这里的要求是解中不能包含重复的组合。我们一下就能想到，把符合题意的解放入unordered_map或者unordered_set中，每次有新的解，就去容器中find一下，如果find的结果等于容器的end()，那么就说明没有重复解，再次加入容器即可。然后理想很丰满，现实很骨感，这样的判断很容易导致超时。那么有什么更好的方法呢？既然在遍历过程中已经对所有情况进行了搜索，何不在搜索过程中就进行重复判断，比如这道题的示例1中，[1,7]和[7,1]都是会被搜索到的，那么怎么判断这两者重复了呢？答案就是排序，排完序后都是[1,7]。排序也分为两种情况，第一种是找到答案后再排序，这样无疑复杂度会很高，并且还是需要对结果进行判重，需要用到unordered_map或者unordered_set。第二种则是对初始数组进行排序，这样原数组就变成了[1,1,2,5,6,7,10]，在搜索过程中会遇到两次[1,7],那么只需要判断：如果当前节点是否和前一个节点相同，并且在前一个节点使用过，那么当前节点就不能使用。此时可以利用一个vector<bool> used来保存每个节点的使用状态，要注意的是，判重是在同一层进行的，不同层之间used是不影响的。我们用一个例子来画一下树状图，比如nums = [1,1,2]，target = 3

总体代码如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(int target, const vector<int>& candidates, int startIndex, vector<bool> used){
        int sum = 0;
        for(int j = 0; j < path.size(); j++){
            sum += path[j];
        }   
        if(sum == target){
            result.push_back(path);
            return;
        }else if(sum > target)return ; // 剪枝

        for(int i = startIndex; i < candidates.size(); i++){
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false){ // 判重
                continue;
            }
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(target, candidates, i + 1, used);
            used[i] = false; // 回溯
            path.pop_back(); // 回溯
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end()); // 记住要排序
        backtracking(target, candidates, 0, used);
        return result;
    }
};

当然，这里还有优化的空间，比如在递归调用中，每次进入下一层之后才会计算path的和，我们可以将sum放入backtracking的参数中，在进入下一层之前计算当前sum + candidates[i]的和是否大于target，如果大于的话就break，可以减少递归调用。

3. 去重问题的特殊情况

下面我们来看一下Leetcode - 491，这道题需要找到数组中不同的递增子序列。这就说明我们不能对原数组进行排序。那么就会给判重增加一定的难度，但是想到使用map和set增加的复杂度，我们依然使用在搜索过程中进行判重的方法。在示例1的搜索过程中，会依次遍历到[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[4,7]，这里就产生了重复，我们画一下抽象树性图：

此时可以看到，导致重复的原因是同一层内出现了重复的元素，那么判重方法就是在同一层内判断当前节点的值是否和之前的所有值有相同情况出现。简单的增加一个判重函数即可。

//判断从[startIndex, i)内有没有和nums[i]相等的元素，有就判定为重复
    bool isRepeat(const vector<int>& nums, int start, int end){
        for(int i = start;i < end; i++){
            if(nums[i] == nums[end])return false;
        }
        return true;
    }

其中start是递归for循环中startIndex的位置，end为递归for循环中i的位置。这样判重就可以方便的降低复杂度，避免了map和set的使用。

总体代码如下：

class Solution {
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(const vector<int>& nums, int startIndex){
        if(path.size() >= 2){ // path中至少存了2两个数就可以放入result中了
            result.push_back(path); // 并且由于需要遍历所以不需要return
        }
        for(int i = startIndex; i < nums.size(); i++){
            //如果 i 不等于 startIndex 并且重复，那么就跳过当前值
            if(i != startIndex && !isRepeat(nums, startIndex, i))continue;
            if(startIndex == 0 || nums[i] >= path.back()){ // 第一个数和满足条件的数要放入
                path.push_back(nums[i]);
                backtracking(nums, i + 1);
                path.pop_back();
        }
        }   
    }
    //判断从[startIndex, i)内有没有和nums[i]相等的元素，有就判定为重复
    bool isRepeat(const vector<int>& nums, int start, int end){
        for(int i = start;i < end; i++){
            if(nums[i] == nums[end])return false;
        }
        return true;
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};