yxc题解（对时间复杂度的分析） $O(n×n!)$

详细题解 ：DFS求全排列总结

枚举每个位置放什么数

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        path = vector<int>(nums.size());
        st = vector<bool>(nums.size());
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return ;
        }
        for (int i = 0; i < nums.size(); i ++) { //这里是枚举每一个数，当st[i] == true;时 i++，看下一个数
            if (st[i] == false) {
                path[u] = nums[i]; // ！！这里写成path[i] = nums[u]也是对的，这就成了 枚举每个数放在什么位置了！
                // path.push_back(nums[i]); //这样是错的， 因为path中的值不断在增多 (也可以用path.push_back(nums[i]) 但是记得后面要pop_back(), 并去掉初始化的 path = vector<int>(nums.size());
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
            }
        }
    }
};

只有两个字母之差：
path[u] = nums[i]; //将未使用过的数字放到指定位置

path[i] = nums[u]; //将指定数字放入未使用的位置

**8