47.全排列II
#回溯 2024-09-21 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
    set<int> recordFirst;
    vector<vector<int>> result;
    vector<int> path;
public:
    void backtrace(vector<int>& nums){
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        set<int> recordSecond;
        for(int i = 0; i < nums.size(); i++){
            
            // 去重同一个元素（由下标判断）
            if(recordFirst.find(i) != recordFirst.end()){ 
                continue;
            }

            // 去重同一个 path
            if(recordSecond.find(nums[i]) != recordSecond.end()){ 
                continue;
            }
            
            path.push_back(nums[i]);
            recordFirst.insert(i);
            recordSecond.insert(nums[i]);
            backtrace(nums);
            recordFirst.erase(i);
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backtrace(nums);
        return result;
    }
};

这道题很好体现 树层和树枝的去重，树层去重需要创建一个局部记录项，树枝去重需要创建一个全局记录项。因为树枝在不同的栈中，树层在同一个栈中。

47.全排列II.png

由于数组中有相同的元素，树枝去重记录项 recordFirst 记录下标，因为下标是唯一的；树层去重记录项 recordSecond 记录元素，因为相同的元素意味着重复行为，是移除的对象。