题目：90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集
（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
一、模式识别
1.子集问题
子集问题是边访问边收集结果，
不仅在回溯树叶节点收集结果，
因此return和收集结果命令不在一起
2.搜索集
单独搜索集，
无重复元素和重复选取
终止条件是最简单的访问到终点
二、代码实现
同层重复剪枝有多种实现方式：
1.基于同层索引去重
简单判断：
class Solution:def backtracking(self, nums, start_idx, path, ans):ans.append(path[:])if start_idx == len(nums):returnfor i in range(start_idx, len(nums)):if i > start_idx and nums[i] == nums[i - 1]:continuepath.append(nums[i])self.backtracking(nums, i + 1, path, ans)path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []nums.sort()self.backtracking(nums, 0, [], ans)return anssame_level数组去重：
代码随想录中把层与层之间传递的数组称为used，
预定义为True，访问后改为False，回溯时改回来
我觉得这样有点不好理解，
所以我把这个数组名称改为same_level，检视是否为同层，
这样True和False的机制就好理解多了
class Solution:def backtracking(self, nums, start_idx, same_level, path, ans):ans.append(path[:])if start_idx == len(nums):returnfor i in range(start_idx, len(nums)):if i > 0 and nums[i] == nums[i - 1] and same_level[i - 1]:continuepath.append(nums[i])same_level[i] = Falseself.backtracking(nums, i + 1, same_level, path, ans)same_level[i] = Truepath.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []nums.sort()same_level = [True] * len(nums)self.backtracking(nums, 0, same_level, [], ans)return ans2.基于数值哈希去重
used数值集合(set)：
class Solution:def backtracking(self, nums, start_idx, path, ans):ans.append(path[:])if start_idx == len(nums):returnused = set()for i in range(start_idx, len(nums)):ch = nums[i]if ch in used:continuepath.append(ch)used.add(ch)self.backtracking(nums, i + 1, path, ans)path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []nums.sort()self.backtracking(nums, 0, [], ans)return ansused数值数组(list)：
代码随想录中的
class Solution:def backtracking(self, nums, start_idx, path, ans):ans.append(path[:])if start_idx == len(nums):returnused = [False] * 21for i in range(start_idx, len(nums)):ch = nums[i]if used[ch + 10]:continuepath.append(ch)used[ch + 10] = Trueself.backtracking(nums, i + 1, path, ans)path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []nums.sort()self.backtracking(nums, 0, [], ans)return ans三、从两类代码写法中看排序的作用
1.两类写法去重机制上的不同
从代码实现部分能看到同层去重有基于同层索引和基于数值哈希两种去重方式
基于索引的前提条件时相同的数值需要挨在一起，
基于数值哈希仿佛没有前提条件，凭借哈希表可以常数时间找到同层重复
也就是说数值哈希仿佛不需要排序了，
是这样吗？
做个测试
2.测试：去排序的数值哈希实现
测试代码：
class Solution:def backtracking(self, nums, start_idx, path, ans):ans.append(path[:])if start_idx == len(nums):returnused = set()for i in range(start_idx, len(nums)):ch = nums[i]if ch in used:continuepath.append(ch)used.add(ch)self.backtracking(nums, i + 1, path, ans)path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []# nums.sort()self.backtracking(nums, 0, [], ans)return ans测试用例：
nums = [4,4,4,1,4]
测试结果：
输出
[[],[4],[4,4],[4,4,4],[4,4,4,1],[4,4,4,1,4],[4,4,4,4],[4,4,1],[4,4,1,4],[4,1],[4,1,4],[1],[1,4]]
预期结果
[[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
3.排序的两重作用
先说结论：排序有把相同数字紧贴和防止异层重复访问两个作用
解释探究过程：
测试结果表明，
去排序后数值哈希的去重作用消失
为什么去掉了排序数值哈希就失效了呢？
事实上并没有完全失效，如果把数值哈希命令去掉：
输出
[[],[4],[4,4],[4,4,4],[4,4,4,1],[4,4,4,1,4],[4,4,4,4],[4,4,1],[4,4,1,4],[4,4,4],[4,4],[4,4,1],[4,4,1,4],[4,4,4],[4,1],[4,1,4],[4,4],[4],[4,4],[4,4,1],[4,4,1,4],[4,4,4],[4,1],[4,1,4],[4,4],[4],[4,1],[4,1,4],[4,4],[1],[1,4],[4]]
说明去排序的数值哈希还是有一点作用的，但没有达到要求
观察两个输出会发现，
数值哈希的确会起到同层去重的作用，
只是由于没有排序，重复虽然不会在同层出现，
但可能会在层与层之间出现重复
也就是说，排序的作用除了让相同数字紧贴方便基于索引的方式去重外
还有把所有可能发生的重复集中在一层中，
防止重复出现在回溯树的多个层中
