题目描述

给定一个含不同整数的集合，返回其所有的子集。

样例 1：

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

样例 2：

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

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

题目讲解

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

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

求解子集的过程:

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

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

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

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

源码

解法1：递归方式

class Solution:    """    @param S: The set of numbers.    @return: A list of lists. See example.    """    # return the subset of nums list        def subsets(self, nums):        # self.results = []        if not nums:            return [[]]                    results = []        self.search(sorted(nums), [], 0, results)        return results                def search(self, nums, subset, startIndex, results):        results.append(subset[:])        for index in range(startIndex, len(nums)):            subset.append(nums[index])            self.search(nums, subset, index + 1, results)            subset.pop()

解法2：非递归方式

class Solution:    """    @param nums: A set of numbers    @return: A list of lists    """    def subsets(self, nums):        # write your code here        if not nums:            return [[]]        nums.sort()        results, stack, startIndex = [], [], 0        stack.append(([], 0))        while stack:            subset, startIndex = stack.pop()            results.append(subset[:])            for i in range(startIndex, len(nums)):                subset.append(nums[i])                stack.append((subset[:], i + 1))                subset.pop()        return results

视频加载中...