本文共 1676 字，大约阅读时间需要 5 分钟。

78. Subsets

题目描述：

Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [   [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

分析：题目要求子集中元素非递减排列，因此我们先对原来的集合进行排序。原集合中每一个元素在任一子集中有两种状态：存在 or 不存在。这样在构造子集的过程中，每个元素就有两种选择状态：选择 or 不选择，因此可以构造一颗二叉树，左子树表示选择该层处理的元素，右子树不选择，最后得到的叶子节点就是子集，所有的叶子节点构成了全部的子集。。。例如对于集合[3,4,5]，构造的二叉树如下：

python代码：

class Solution(object):    def subsets(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        self.sub_sets=[]        self.sub_set=[]        nums.sort()        self.dfs(nums,0)        return self.sub_sets            def dfs(self,nums,index):        if index==len(nums):            print self.sub_set            temp=self.sub_set[:]#通过切片，生成sub_set的拷贝，这一步至关重要！！            self.sub_sets.append(temp)#此句不能写成 self.sub_sets.append(self.sub_set)            return         #选择nums[index]        self.sub_set.append(nums[index])        self.dfs(nums,index+1)        #不选择nums[index]        self.sub_set.pop()        self.dfs(nums,index+1)

C++代码：

class Solution {private:    vector
   
    
     >res;public:    vector
     
      
       > subsets(vector
       
        & nums) {        res.clear();        sort(nums.begin(),nums.end());        vector
        
         subset; dfs(nums,0,subset); return res; } void dfs(vector
         
          &nums,int index,vector
          
           &subset) { if(index==nums.size()) { res.push_back(subset); return; } //选择nums[index] subset.push_back(nums[index]); dfs(nums,index+1,subset); //不选择nums[index] subset.pop_back(); dfs(nums,index+1,subset); }};