【代码随想录day 25】 力扣 47.全排列 II

视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html#%E6%8B%93%E5%B1%95
力扣题目：https://leetcode.cn/problems/permutations-ii/

这道题是我自己写的，主要有两种去重操作：

1. 树枝去重，就是同一个树枝下相同元素不会再取一边，注意是相同元素，不是重复元素，也就是下标一样的元素不会重复取用数组bool类型的used实现
2. 是树层去重，我这里用了unordered_set来保证重复的元素不会再取。代码随想录里用的方法是排序之后再进行前一个元素和当前元素的判断
   这是代码随想录里的判断方法：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    
    void backtracking(vector<int> &nums, vector<bool> &used)
    {
        //判断终止条件,如果path的大小等于nums的大小就存入result中
        if(path.size() == nums.size() )
        {
            result.push_back(path);
            return;
        }
        unordered_set<int> uset;
        //单层遍历
        for(int i = 0; i< nums.size(); i++)
        {
            if(used[i] == true || uset.find(nums[i]) != uset.end())
            {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            uset.insert(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;

        }
        return;
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);

        backtracking(nums, used);
        return result;
    }
};