/*
思路1：插入法
对每个数枚举
    对res中的每个path处理
        对当前path挨个枚举可插入位置
去重方法：对每个数按顺序枚举

思路2：多叉树dfs + 回溯
枚举path中每个位置（dfs）
    枚举所有nums中的元素，插入该位置（多叉树）
nums = [1, 2, 3]
        1
   /    |    \
  1     2     3
 /|\   /|\
1 2 3 1 2 3
去重方法：使用状态数组标记每个数是否用过

思路3：枚举法 dfs递归
依次把每个数放在第1位，然后对[2, n]递归
不推荐此方法，因为该思路不能用于 全排列II
*/
/*思路1*/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back(vector<int>());
        for (auto num: nums) {
            vector<vector<int>> new_res;
            for (auto path: res)
                for (int i = 0; i <= res[0].size(); i ++) {
                    vector<int> tmp = path; //深拷贝
                    tmp.insert(tmp.begin() + i, num);
                    new_res.push_back(tmp);
                }
            res = new_res;
        }
        return res;
    }
};
/*思路2*/
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> st;
    vector<vector<int>> permute(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++ ) st.push_back(false);
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int idx) {
        if (idx == nums.size()) {
            if (path.size() == nums.size())
                res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i ++) {
            if (!st[i]) {
                path.push_back(nums[i]);
                st[i] = true;
                dfs(nums, idx + 1);
                path.pop_back();
                st[i] = false;
            }
        }
    }
};
/*思路3*/
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0, nums.size());
        return res;
    }
    void dfs(vector<int>& nums, int start, int finish) {
        if (start == finish) {
            res.push_back(nums);
            return;
        }
         for (int i = start; i < finish; i ++) {
            swap(nums[i], nums[start]); //将nums[i]放在当前第一位
            dfs(nums, start + 1, finish);
            swap(nums[i], nums[start]); //回溯
        }
    }
};