题目描述

给定一个可能具有重复数字的列表，返回其所有可能的子集。

子集中的每个元素都是非降序的两个子集间的顺序是无关紧要的解集中不能包含重复子集

样例 1：

输入：[0]输出：[  [],  [0]]

样例 2：

输入：[1,2,2]输出：[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

你可以同时用递归与非递归的方式解决么？

题目讲解

算法武器：排序（以方便我们去重） + dfs深度优先遍历+递归

本题和combination sum的题目类似，都是要求解出所有的子集，对于combination sum，还进一步要求在子集中过滤符合条件的解（元素和等于给定target），然后才能将其加入全局解。而本题仅要求求解所有子集，所以比较简单。当然在求解过程中，我们都需要对自己进行去重操作，为了有效去重，我们必须保证给定的输入是经过排序的。

求解子集的过程:

遍历给定集合中的每一个元素，每一个元素都可以选择加入子集或者不加入子集，然后由此进行递归，递归调用结束之后，我们需要进行回溯。

subsets这道题目是首先将当前局部subset集合加入解集得，然后尝试构造新的解，缩小问题规模，进一步递归调用。

dfs函数的定义是递归的：在给定的集合中按序选择一个元素尝试将其加入到局部变量/局部子集subset中（本次尝试结束之后需要回溯），然后递归调用自己，在剩下的集合中（这是一个规模更小的集合，集合尺寸被startIndex限定），做相同的事情，直到做完所有的尝试。

dfs就是对解决问题的当前步骤做各种尝试，每种尝试都会缩小问题的规模，解决问题的一小部分，每种尝试都是一次递归，每种递归都会产生一颗搜索子树，子树中包含很多可能的解。每个递归都会查看是否局部解已经满足条件，进而将其加入全局解。

源码

class Solution:    """    @param nums: A set of numbers.    @return: A list of lists. All valid subsets.    """    def subsetsWithDup(self, nums):        # write your code here        if not nums:            return [[]]                    result = []        nums.sort()        self.helper(nums, 0, [], result)                return result            # 首先将给定的subset加入到结果集中，然后再从startIndex位置开始，选入一个元素加入到subset，然后递归调用    def helper(self, nums, startIndex, subset, result):        result.append(subset[:])        for i in range(startIndex, len(nums)):            # 进行去重            if i > startIndex and nums[i] == nums[i - 1]:                continue                        subset.append(nums[i])            # 注意这里的传入的是i+1, 不是startIndex + 1， 有很多人在这里搞错            self.helper(nums, i + 1, subset, result)            # 回溯            subset.pop()

视频加载中...