leetcode46题解
acwing51等价于leetcode47题，参考leetcode 46思路1和思路2

/*
思路1：
保持重复元素相对位置不变
思路1：插入法
对每个数字进行枚举
    对res中每个path枚举
        对path中每个插入位置枚举
        （如果插入位置前一位是相同数字就直接结束本次循环，保证同数值，相对顺序不变）

思路2：多叉树dfs + 回溯
枚举path中每个位置（dfs）
    枚举所有nums中的元素，插入该位置（多叉树）
首先对nums排序
状态数组记录每个元素（下标）是否已经被使用，如果前一个相同的元素已被使用过，就直接跳过本path
（保证nums[i+1]/后面的数都在nums[i]/前面的数之前插入path，保证同数值相对顺序不变 ）
(如果nums=[1,1,1], 分别标记为[1_1, 1_2, 1_3], 那么会出现[1_1, 1_3]这种错误排列
但是一旦前面出现1_1, 1_2永远无法被插入到path中，最终该path全部continue掉)
*/
/*思路1*/
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res(1, vector<int>());
        for (auto num: nums) {
            vector<vector<int>> new_res;
            for (auto path: res)
                for (int i = 0; i <= path.size(); i ++) {
                    if (i == 0 || path[i-1] != num) {
                        vector<int> tmp = path; //深拷贝
                        tmp.insert(tmp.begin()+i, num);
                        new_res.push_back(tmp);
                    }
                    else break;
                }
            res = new_res;
        }
        return res;
    }
};
/*思路2*/
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path, st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        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()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i ++) { //枚举path[idx]位置处的元素
            if (st[i] || (i > 0 && nums[i]==nums[i-1] && st[i-1])) continue;
            path.push_back(nums[i]);
            st[i] = true;
            dfs(nums, idx+1);
            path.pop_back();
            st[i] = false;
        }
    }
};