力扣-46-全排列

回溯法模板题

回溯法

感觉这个方法的题目都比较难，全是中等

回溯算法本质上是对深度优先遍历DFS的优化，当已经到达终点/已经没有可以选择（选择都访问过了）的时候，，就向上回退一步
这里引入了一个概念叫“状态”——每一个节点表示了求解问题的不同阶段，而每一次回溯都需要“重置状态”（这在算法中的体现通常是一个方法）

class Solution {
    // 解题思路：看作是填从左往右n个空格
public:
// 递归函数
// 参数：用于保存结果的二维数组、当前排列数组、从左往右第first个位置、单个结果数组长度（即题目给的可用数字数组的长度）
    void backtrack(vector>& res, vector& output, int first, int len){
        // 当已经填到最后一个位置，则将这个结果数组放入二维数组中
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 这个first在for循环中是不会变的，一直都是层数——也可以说是要填的第几个位置
            // 动态维护数组，把选中的换到左边去
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作，因为下面的可能性都跑完了，要恢复output数组以供下一次循环使用
            swap(output[i], output[first]);
        }
    }
    vector> permute(vector& nums) {
        vector > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

百思不得其解的是这两个相同的交换步骤是什么意思
题解的说法是说把数组分成两个部分，左边是已经填过，右边是待填的数，然后这两步就是维护这个数组的

还有就是这个for循环和递归
递归过程应该是填一个序列的