【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