子集II

Leetcode Link: 90. 子集 II - 力扣（LeetCode）

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

解法一

思路：和子集问题十分类似，区别在于输入的 nums 中可能有重复的元素，这就导致有可能使用该问题的代码会导致子集中出现重复的元素。

为了避免这种情况，本题中需要在回溯的过程中进行去重

本题的去重是去掉”同一层”的重复，因此只需要排序后判断当前的值和上一个值是不是一样的就可去重了

同样的思路出现在组合总和II 中，但是那里面用的是 used，也需要先排序才行。同样的，那里面也能用本文的方式，更快更小。 为什么他用了 used还要排序？

题解：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtracking(choose):
            nonlocal res, path
 
            res.append(copy.deepcopy(path))
 
            if choose == []:
                return 
            # 初始化前一个的值
            last_val = float('inf')
            for idx, val in enumerate (choose):
	            # 去重，用过的不用了
                if val == last_val:
                    continue
                last_val = val
                path.append(val)
                backtracking(choose[idx+1:])
                path.pop()
            
        res = []
        path = []
        nums.sort()
        backtracking(nums)
        return res
 

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系