[Vssue]0047.全排列II.md

[youngyangyang04]

https://www.programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

[JetJie]

我理解的是used[i - 1] == false，既然同层前一位没有使用过，那就用前面的，不要用后面的，因为前面的需要更少的遍历时间。

[Du1in9]

private void backtracking(int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        paths.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) 
                continue;
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums, used);
            used[i] = false;
            path.remove(path.size() - 1); 
        }
    }
}

// 深度1: backtracking([1,1,2], 0), path = [], used = [f,f,f]
i = 0：path = [0]，递归 backtracking([1,1,2], 1)。回溯，path = []
i = 1：满足 1 == 1 && used[0] == false，继续遍历（去重）
i = 2：path = [2]，递归 backtracking([1,1,2], 3)。回溯，path = []
// 深度2: 例: backtracking([1,1,2], 1), path = [1], used = [t,f,f]
i = 0：满足 used[0] == true, 继续遍历（去重）
i = 1：path = [1,1]，递归 backtracking([1,1,2], 3)。回溯，path = [1]
i = 2：path = [1,2]，递归 backtracking([1,1,2], 3)。回溯，path = [1]
// 深度3: 例: backtracking([1,1,2], 2), path = [1,1], used = [t,t,f]
i = 0：满足 used[0] == true, 继续遍历（去重）
i = 1：满足 used[1] == true, 继续遍历（去重）
i = 2：path = [1,1,2]，递归 backtracking([1,1,2], 3)。回溯，path = [1,1]

[Du1in9]

@JetJie

我理解的是used[i - 1] == false，既然同层前一位没有使用过，那就用前面的，不要用后面的，因为前面的需要更少的遍历时间。

我认为 used 是指的上一层是否使用过，可以类比 used[i] == true 所以跳过。而这里的 used[i - 1] == false 作用是：如果上一层前一位没有使用过，那就这一层使用。这一层是如何使用的呢？答案是既然已经到了这一位，那前一位就一定使用过，因为除非上一层使用过，那前一位就一定会回溯为 false！

[ZYKWLJ]

@Du1in9

@JetJie

我理解的是used[i - 1] == false，既然同层前一位没有使用过，那就用前面的，不要用后面的，因为前面的需要更少的遍历时间。

我认为 used 是指的上一层是否使用过，可以类比 used[i] == true 所以跳过。而这里的 used[i - 1] == false 作用是：如果上一层前一位没有使用过，那就这一层使用。这一层是如何使用的呢？答案是既然已经到了这一位，那前一位就一定使用过，因为除非上一层使用过，那前一位就一定会回溯为 false！

我的理解是 首先核心点：树层去重、树枝去重两者必选其一。

因为树层去重控制着下面的树枝去重（因为可理解为在树层的基础上再往下开花），所以树层去重效率更好。

其次解释为什么是used[i]=false，又为什么要跳过：

回退到同层时，used数组已经是全归FALSE了（以第一层为例子），所以同层的元素本身所有使用就是FALSE，这时候再来num[i-1]=num[i],就意味着前面的nums[i-1]使用过的情况，会重新发生在nums[i]之上，所以要去重。就要跳过这种情况。那为什么一定要选used[i]=false呢？因为如果是true，就代表着不同索引的元素在一条树枝上排列，排列出来的元素会相同，但是结果集只有这一个。所以一定是used[i]=false，而且一定要跳过

[walterke1001]

这个去重的方法太抽象了。 还是这样判定比较好理解：used[]数组用于同一枝去重，set集合用于同一层去重

[LiNanyan2001]

用哈希表存放搜索次数来进行，可以同时树枝去重和树层去重 class Solution { public: vector<vector> ans; vector path; void dfs(vector& nums, unordered_map<int,int> &m) { if (path.size() == nums.size()) { ans.push_back(path); return; } for (auto it=m.begin();it!=m.end();++it) { if (it->second==0) { // 搜索次数已用完，不再搜索 continue; } --it->second; path.push_back(it->first); dfs(nums, m); path.pop_back(); ++it->second; } } vector<vector> permuteUnique(vector& nums) { unordered_map<int,int> m; for(auto n:nums){ ++m[n]; } dfs(nums, m); return ans; } };