超易懂的回溯法【C++】

   回溯法是一种经典的算法，它的思想是按条件向前搜索，以达到目标；但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术就是回溯法。

  回溯法的一个常规应用场景就是全排列，比如给定一个数组，我们要求输出它的全排列，首先来直接看看完整的代码。（C++）

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
public:
    void backtrack(vector>& res, vector& output, int first, int len){
        //构成了一个排列了
        if (first == len) {
            res.emplace_back(output);  //将一个全排列output存入res中
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 回溯操作
            swap(output[i], output[first]);
        }
    }
    vector> permute(vector& nums) {
        vector > res;  //构造容器res
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};
//res是输出的结果，output是给一个排列

 就这么看看，代码有点儿难懂，别急，我们一点点儿来看！

首先来看看permute这个全排列函数

vector> permute(vector& nums) {
        vector > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }

permute函数平平无奇，常规操作，首先是构造了一个二维容器res，res里面的就是我们要返回的答案，然后它调用了回溯函数，注意传入的first = 0。

接下来看看回溯函数：

  我们可以首先想想，在构造全排列的时候我们是怎么构造呢？一个直接的想法就是比如我有一个全排列A，A本来是空的，我将每个元素一个个的放入A中，当所有元素都放入A中了，一个全排列就构成了。

  这里我们也是这个思想，只不过A不是空的了，他是一个包含所有元素的排列nums了，我们可以对nums进行元素交换构造全排列。怎么才能不重不漏呢？

  我们沿用构造A的思想，题目中的nums只有三个元素不直观，我们这儿不妨让nums有五个元素[1,2,3,4,5]，现在我往A中放了两个元素[3,5]，那么我们只需要nums[0]与nums[2]交换，nums[1]与nums[4]交换，这时候nums变为了[3,5,1,4,2]，我们可以在第三个元素1这儿设置一个标志位first = 2，它表示nums[first]之前的元素都是已经放到了A当中的，因为first=2，所以已经排好了两个元素，当我们不断放入元素，first=5的时候就所有元素都放入A中了，形成了一个全排列。代码如下，len是nums的长度，当first等于len时，通过交换形成一个全排列output，利用emplace_back函数将这个全排列存入res这个容器中。

if (first == len) {
            res.emplace_back(output);
            return;
        }

 接下来就是回溯操作了，一开始传入的first = 0,代表此时还没有元素放入了A当中，output[i]与output[first]交换，就是将第i - 1个元素放入A中，这时候排好了一个元素，则first + 1，开始排剩下的元素，于是调用backtrack(res, output, first + 1, len)。但是如果我们现在不想这么快就排第i - 1个元素呢，那么我们之前的swap(output[i], output[first])就排错了，需要再交换一次将元素交换回来，于是就有了回溯操作swap(output[i], output[first])。

for (int i = first; i < len; ++i) {

            // 动态维护数组

            swap(output[i], output[first]);

            // 继续递归填下一个数

            backtrack(res, output, first + 1, len);

            // 回溯操作

            swap(output[i], output[first]);

        }

我们最后再来看一遍完整代码，是不是清晰多了呢

class Solution {
public:
    void backtrack(vector>& res, vector& output, int first, int len){
        //构成了一个排列了
        if (first == len) {
            res.emplace_back(output);  //将一个全排列output存入res中
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 回溯操作
            swap(output[i], output[first]);
        }
    }
    vector> permute(vector& nums) {
        vector > res;  //构造容器res
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};
//res是输出的结果，output是给一个排列

ps:如果有哪儿写的不太清楚欢迎留言，我会及时改进，如果哪儿写的有问题也欢迎指正

参考出处：https://leetcode.cn/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/