引言

回溯算法是一个很直白的算法，它被用来做路径的遍历等等。所谓的回溯就是每一次决策我会选择一条路走，递归的这样处理，如果无路可走的时候，或者已经到达终点的时候，那么我就回溯到上一步，然后选择另一条路，直到做完所有的选择位置。

通过上面的描述，跟dfs很像啊。实际上回溯就是dfs的思想。

回溯算法的模板

result = []
def backtrack(路径, 选择列表):
    if 不满足条件
        return
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

举例说明

回溯算法最著名的例子莫过于N皇后问题，下面我们就来分析下

N皇后问题

leetcode上面有两个N皇后的问题，51. N 皇后, 52. N皇后 II.
其中第一个更难一点，我们就以这个为例子。

套用我们的模板

首先定义backTrack
在backTrack内，首先处理conflict，这相当于提前剪枝
当所有路径都走完了以后，对其进行处理，拼接输出结构
for循环去为第index步选择一条路，选完这条路后，递归调用backTrack为index+1步选路。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<int> queuePos(n);
        backTrack(0, n, queuePos);
        return ret;
    }

    void backTrack(int index, int n, vector<int> queuePos) {
        if (conflict(index, queuePos)) {
            return;
        }

        if (index == n) {
            vector<string> solution = print(queuePos, n);
            ret.push_back(solution);
            return;
        }

        for (int i = 0; i < n; i++) {
            queuePos[index] = i;
            backTrack(index + 1, n, queuePos);
        }
    }

    vector<string> print(vector<int> queuePos, int n) {
        vector<string> solution;
        for (int i = 0; i < n; i++) {
            string tmp(n, '.');
            tmp[queuePos[i]] = 'Q';
            solution.push_back(tmp);
        }
        return solution;
    }

    bool conflict(int index, vector<int> queuePos) {
        for (int i = 0; i < index - 1; i++) {
            if (queuePos[i] == queuePos[index - 1] || abs(queuePos[index - 1] - queuePos[i]) == abs(index - 1 - i)) {
                return true;
            }
        }
        return false;
    }
private:
    vector<vector<string>> ret;
};

全排列问题（不包含重复元素）

全排列问题跟上面的N皇后问题是不一样的，主要有两点

没有剪枝
需要加一个标志位，来判定相应的数据有没有被使用。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size());
        vector<int> oneSolution(nums.size());
        backTrack(0, nums, visited, oneSolution);
        return ret;
    }

    void backTrack(int index, vector<int>& nums, vector<bool>& visited, vector<int>& oneSolution) {
        if (index == nums.size()) {
            ret.push_back(oneSolution);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (visited[i]) {
                continue;
            }
            oneSolution[index] = nums[i];
            visited[i] = true;
            backTrack(index+1, nums, visited, oneSolution);
            visited[i] = false;
        }
    }
private:
    vector<vector<int>> ret;
};

全排列问题（包含重复元素）

同样是全排列问题，但是这个题目是需要去重的，这就增加了难度了。

一种方案是生成结果以后再去重。但是这样明显效率不高。另一种方式就是提前剪枝。

首先将数组元素排序，然后利用下面的条件剪枝

1
2
3

if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
    continue;
}

具体的代码实现如下：


class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> visited(nums.size());
        vector<int> oneSolution(nums.size());
        sort(nums.begin(), nums.end());
        backTrack(0, nums, visited, oneSolution);
        return ret;
    }

    void backTrack(int index, vector<int>& nums, vector<bool>& visited, vector<int>& oneSolution) {
        if (index == nums.size()) {
            ret.push_back(oneSolution);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            oneSolution[index] = nums[i];
            visited[i] = true;
            backTrack(index+1, nums, visited, oneSolution);
            visited[i] = false;
        }
    }
private:
    vector<vector<int>> ret;
};

另外，这道题发现了一种利用C++API的方法，也是绝绝子。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(begin(nums), end(nums));
        do {
            ret.emplace_back(nums);
        } while (next_permutation(begin(nums), end(nums)));
        return ret;
    }
};

总结

回溯算法是不是一种暴力的算法。是的，它本身就是一种暴力穷尽的算法，每一条路径，每一个选择挨个尝试。只不过在回溯的时候，伴随着提前剪枝，这样相对于穷举，可以极大的提升效率。同时回溯算法的应用场景本身就是为了找到所有的路线，因此伴随着剪枝，回溯算法已经算是高效的算法了。