【LeetCode 中等题】41-子集

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
           

解法1。迭代

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        import copy
        if not nums:
            return
        res = [[]]
        nums.sort()
        for i in range(len(nums)):
            m = len(res)
            for j in range(m):
                # 这个地方经过验证，不能直接appendres[j]，因为append后不是不同于前一个list，而是创建了2个指向同一个list的对象
                # 所以，当我们操作最后一个元素时，其他所有复制的元素内容也会发生变化，亲测
                tmp = copy.copy(res[j]) 
                res.append(tmp)
                res[-1].append(nums[i])
        return res   
           

解法2。递归，DFS。

由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

[]        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []          

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        sub =[]
        res = []
        self.helper(nums, sub, res, 0)
        return res
    def helper(self, nums, sub, res, index):
        res.append(sub[:])
        for i in range(index, len(nums)):
            sub.append(nums[i])
            self.helper(nums, sub, res, i+1)
            sub.pop()
        return
           

参考链接：http://www.cnblogs.com/grandyang/p/4309345.html