【Leetcode刷题记录】46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

全排列就是要找出数组里所有元素的所有排序方式。你得一个一个试着把每个数字放在不同的位置上，看看能组成哪些排列。可以采用回溯法+深度优先遍历DFS的方法求解。

以[1,2,3]为例，每一次尝试抽象形成的树型结构如图所示：

对于这颗树，从根节点开始进行深度优先遍历

[]–>[1]–>[1,2]–>[1,2,3]–>[1,2]–>[1]–>[1,3]–>…

回溯法三部曲

1. 确定递归函数的参数和返回值
   在搜索过程中，每一个元素都有一个使用和未使用的标记，所以需要使用一个标记数组来记录哪些元素已经使用过，同时需要一个路径数组来记录当前构建的排列。

   void backtrack(vector<int>& nums, vector<int>& cur, vector<int>& vis);
   

   函数没有显式的返回值，而是通过修改全局变量res（存储所有可能排列的结果集）来间接输出结果。

2. 确定递归函数的终止条件
   观察上述树型结构，在叶子节点处，路径数组长度等于原数组长度时，表示已经找到了一个完整的排列，此时将当前路径加入结果集，并结束当前递归。

   if (cur.size() == nums.size()) {
       res.push_back(cur);
       return;
   }
   

3. 确定递归函数的单层逻辑
   单层逻辑指的是在每一层递归调用中执行的操作，主要包括以下几个步骤：

   1. 遍历未使用的元素：循环遍历整个nums数组，尝试将每个未被访问过的元素（!vis[i]）加入当前排列cur中。
   2. 做出选择：一旦选择了某个元素（假设索引为i），首先标记为已访问（vis[i] = 1），然后将添加到当前排列cur中。
   3. 继续递归：调用自身backtrack(nums, cur, vis)，尝试寻找剩余元素的排列。
   4. 撤销选择（回溯）：在递归调用结束后，撤销之前的选择，将当前元素从排列cur中移除（cur.pop_back()），并将访问标记vis[i]重置为0(千万不要忘了这一步)，以便尝试其他可能的排列。

vector<vector<int>> res;
void backtrack(vector<int>& nums, vector<int>& cur, vector<int>& vis) {
    // 如果当前路径长度等于原数组长度，则找到了一个完整排列
    if (cur.size() == nums.size()) {
        res.push_back(cur);
        return;
    }
    // 遍历所有元素，尝试每个未被访问过的元素
    for (int i = 0; i < nums.size(); i++) {
        if (!vis[i]) {
            vis[i] = 1; // 标记为已访问
            cur.push_back(nums[i]); // 做出选择
            backtrack(nums, cur, vis); // 继续递归构建
            cur.pop_back(); // 撤销选择（回溯）
            vis[i] = 0; // 取消标记
        }
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    int len = nums.size();
    if (len == 0) {
        return {}; 
    }
    vector<int> cur; // 当前构建中的排列
    vector<int> vis(len, 0); // 访问标记数组
    backtrack(nums, cur, vis); // 启动回溯过程
    return res;
}